Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems

DOI10.1016/S0020-0190(97)00024-0zbMath1336.05138OpenAlexW2088959951MaRDI QIDQ287003

Hans L. Bodlaender, Dimitrios M. Thilikos

Publication date: 26 May 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)00024-0

zbMATH Keywords

algorithmstreewidthcombinatorial problemsanalysis of algorithmsapproximation algorithmsgraph minors

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25)

Related Items

Degree-constrained decompositions of graphs: Bounded treewidth and planarity ⋮ Finding geometric representations of apex graphs is NP-hard ⋮ Recognizing geometric intersection graphs stabbed by a line ⋮ \(\mathcal{P}\)-apex graphs ⋮ Some vertex/edge-degree-based topological indices of \(r\)-apex trees

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. V. Excluding a planar graph
• Quickly excluding a forest
• Quickly excluding a planar graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Characterization and Recognition of Partial 3-Trees
• Applications of a Planar Separator Theorem
• An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
• On Linear Time Minor Tests with Depth-First Search
• Approximation algorithms for NP-complete problems on planar graphs
• ON DISJOINT CYCLES
• On Linear Recognition of Tree-Width at Most Four
• Node-and edge-deletion NP-complete problems
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth