Welcome!
To use the personalized features of this site, please log in or register.
If you have forgotten your username or password, we can help.
My Menu
Saved Items

The Forest Wrapping Problem on Outerplanar Graphs

Isabella LariContact Information, Federica RiccaContact Information and Andrea ScozzariContact Information

(5)  Dip. Statistica, Probabilità e Statistiche Applicate, Università di Roma “La Sapienza”, Italy
(6)  Dip. Matematica per le Decisioni Economiche, Finanziarie ed Assicurative Università di Roma “La Sapienza”, Italy
Abstract
In this paper we study the Forest Wrapping Problem (FWP) which can be stated as follows: given a connected graph G = (V,E), with ∣V ∣ = n, let π0 be a partition of G into K (not necessarily connected) components, find a connected partition π* of G that wraps π0 and has maximum number of components. The Forest Wrapping problem is NP-complete on grid graphs while is solvable in O(n log n) time on ladder graphs. We provide a two-phase O(n 2 ) time algorithm for solving FWP on outerplanar graphs.

Keywords  Outerplanar graphs - Connected partition - Steiner Forest - Maximum Split Clustering


Contact Information Isabella Lari
Email: isabella.lari@uniroma1.it

Contact Information Federica Ricca
Email: federica.ricca@uniroma1.it

Contact Information Andrea Scozzari
Email: andrea.scozzari@uniroma1.it
Fulltext Preview (Small, Large)
Image of the first page of the fulltext

References secured to subscribers.



Export this chapter
Export this chapter as RIS | Text
 
Remote Address: 38.107.191.109 • Server: mpweb03
HTTP User Agent: CCBot/1.0 (+http://www.commoncrawl.org/bot.html)