We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new N P-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O (n log n)) time algorithm for such problems in graphs with vertex degree bounded by 3. © 2009 Elsevier B.V. All rights reserved.
On the complexity of some subgraph problems / Andrea, Scozzari; Tardella, Fabio. - In: DISCRETE APPLIED MATHEMATICS. - ISSN 0166-218X. - STAMPA. - 157:17(2009), pp. 3531-3539. [10.1016/j.dam.2009.04.003]
On the complexity of some subgraph problems
TARDELLA, Fabio
2009
Abstract
We study the complexity of the problem of deciding the existence of a spanning subgraph of a given graph, and of that of finding a maximum (weight) such subgraph. We establish some general relations between these problems, and we use these relations to obtain new N P-completeness results for maximum (weight) spanning subgraph problems from analogous results for existence problems and from results in extremal graph theory. On the positive side, we provide a decomposition method for the maximum (weight) spanning chordal subgraph problem that can be used, e.g., to obtain a linear (or O (n log n)) time algorithm for such problems in graphs with vertex degree bounded by 3. © 2009 Elsevier B.V. All rights reserved.I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.
