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

DOI10.1016/S0020-0190(97)00024-0zbMATH Open1336.05138OpenAlexW2088959951MaRDI QIDQ287003FDOQ287003

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

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

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)

Cites Work

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

Cited In (6)

• Finding geometric representations of apex graphs is NP-hard
• Title not available (Why is that?)
• Some vertex/edge-degree-based topological indices of \(r\)-apex trees
• Recognizing geometric intersection graphs stabbed by a line
• Degree-constrained decompositions of graphs: Bounded treewidth and planarity
• \(\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)