Exact algorithm for the maximum induced planar subgraph problem

DOI10.1007/978-3-642-23719-5_25MaRDI QIDQ3092237zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Fedor V. Fomin, Ioan Todinca, Yngve Villanger

Publication date 16 September 2011

Published in Algorithms – ESA 2011 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-23719-5_25

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• scientific article; zbMATH DE number 2084267
• Approximation Algorithms for the Maximum Induced Planar and Outerplanar Subgraph Problems
• A linear-time algorithm for finding induced planar subgraphs
• On maximum planar induced subgraphs
• Planar induced subgraphs of sparse graphs

Cited in

(21)

• A linear-time algorithm for finding induced planar subgraphs
• Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs
• Exact algorithms for the maximum planar subgraph problem: new models and experiments
• Planar induced subgraphs of sparse graphs
• Fast partitioning l-apex graphs with applications to approximating maximum induced-subgraph problems
• Planar induced subgraphs of sparse graphs
• Quasipolynomiality of the Smallest Missing Induced Subgraph
• The maximum happy induced subgraph problem: bounds and algorithms
• Largest chordal and interval subgraphs faster than \(2^n\)
• Subexponential-time algorithms for finding large induced sparse subgraphs
• On maximum planar induced subgraphs
• Solving the 2-disjoint connected subgraphs problem faster than \(2^n\)
• Lossy planarization: a constant-factor approximate kernelization for planar vertex deletion
• Algorithms for finding an induced cycle in planar graphs
• Compositional properties of alignments
• Large Induced Subgraphs via Triangulations and CMSO
• scientific article; zbMATH DE number 2084267 (Why is no real title available?)
• Cycles to the rescue! Novel constraints to compute maximum planar subgraphs fast
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Scheduling partially ordered jobs faster than \(2^n\)

This page was built for publication: Exact algorithm for the maximum induced planar subgraph problem

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