On the complexity of some subgraph problems

DOI10.1016/j.dam.2009.04.003zbMath1227.05240OpenAlexW1974807686MaRDI QIDQ967414

Andrea Scozzari, Fabio Tardella

Publication date: 28 April 2010

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2009.04.003

zbMATH Keywords

spanning treespanning subgraphschordal graphsedge-deletion\(q\)-trees

Mathematics Subject Classification ID

Trees (05C05) Extremal problems in graph theory (05C35) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Complexity of some graph-based bounds on the probability of a union of events

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the SPANNING \(k\)-TREE problem
• The complexity of regular subgraph recognition
• Maximal chordal subgraphs
• A partial k-arboretum of graphs with bounded treewidth
• On spanning 2-trees in a graph
• On simple characterizations of k-trees
• Finding a Maximum Clique in an Arbitrary Graph
• Graph minors. II. Algorithmic aspects of tree-width
• An Application of Duality to Edge-Deletion Problems
• The complexity of some edge deletion problems
• NC algorithms for recognizing chordal graphs and k trees
• The Effect of a Connectivity Requirement on the Complexity of Maximum Subgraph Problems
• Edge-Deletion Problems
• Series-parallel subgraphs of planar graphs
• Graph Classes: A Survey
• Node-and edge-deletion NP-complete problems
• Complexity classification of some edge modification problems