The Forest Wrapping Problem on Outerplanar Graphs
Isabella Lari5
, Federica Ricca5
and Andrea Scozzari6 
| (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
References secured to subscribers.