On the complexity of some subgraph problems |
| |
Authors: | Andrea Scozzari Fabio Tardella |
| |
Affiliation: | aUniversità di Roma “La Sapienza”, Dip. di Matematica per le Decisioni Economiche, Finanziarie ed Assicurative, Via del C. Laurenziano, 9, 00161 Roma, Italy |
| |
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 NP-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(nlogn)) time algorithm for such problems in graphs with vertex degree bounded by 3. |
| |
Keywords: | Spanning subgraphs Chordal graphs Edge-deletion Spanning tree mml4" > text-decoration:none color:black" href=" /science?_ob=MathURL&_method=retrieve&_udi=B6TYW-4WNPDF2-1&_mathId=mml4&_user=10&_cdi=5629&_rdoc=7&_acct=C000054348&_version=1&_userid=3837164&md5=9e39d913fc35e0b36e3c33aa92c80f81" title=" Click to view the MathML source" alt=" Click to view the MathML source" >q-trees |
本文献已被 ScienceDirect 等数据库收录! |
|