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

DOI10.1016/S0020-0190(97)00024-0MaRDI QIDQ287003zbMATHOpenAlexFDO

Authors Dimitrios M. Thilikos, Hans L. Bodlaender

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

algorithmsanalysis of algorithmstreewidthapproximation algorithmsgraph minorscombinatorial problems

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 2102753
• Efficient Approximation Schemes for Maximization Problems onK3,3-free orK5-free Graphs
• Exact algorithm for the maximum induced planar subgraph problem
• Obtaining a planar graph by vertex deletion
• scientific article; zbMATH DE number 3946182

Cites work

• scientific article; zbMATH DE number 3961650 (Why is no real title available?)
• scientific article; zbMATH DE number 2102753 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• An Approximation Algorithm for the Maximum Independent Set Problem on Planar Graphs
• Applications of a Planar Separator Theorem
• Approximation algorithms for NP-complete problems on planar graphs
• Characterization and Recognition of Partial 3-Trees
• Graph minors. V. Excluding a planar graph
• Homomorphieeigenschaften und mittlere Kantendichte von Graphen
• Node-and edge-deletion NP-complete problems
• ON DISJOINT CYCLES
• On Linear Recognition of Tree-Width at Most Four
• On Linear Time Minor Tests with Depth-First Search
• Quickly excluding a forest
• Quickly excluding a planar graph

Cited in

(6)

• Finding geometric representations of apex graphs is NP-hard
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• Some vertex/edge-degree-based topological indices of \(r\)-apex trees
• Recognizing geometric intersection graphs stabbed by a line
• scientific article; zbMATH DE number 2102753 (Why is no real title available?)
• \(\mathcal{P}\)-apex graphs

This page was built for publication: Fast partitioning \(l\)-apex graphs with applications to approximating maximum induced-subgraph problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q287003)