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 \pi^0 be a partition of G into K (not necessarily connected) components, find a connected partition \pi∗ of G that wraps \pi^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(n2) time algorithm for solving FWP on outerplanar graphs.
The Forest Wrapping Problem on Outerplanar Graphs / Lari, Isabella; Ricca, Federica; A., Scozzari. - STAMPA. - 2573:(2002), pp. 343-352. [10.1007/3-540-36379-3]
The Forest Wrapping Problem on Outerplanar Graphs
LARI, Isabella;RICCA, Federica;
2002
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 \pi^0 be a partition of G into K (not necessarily connected) components, find a connected partition \pi∗ of G that wraps \pi^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(n2) time algorithm for solving FWP on outerplanar graphs.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
