×

Exact algorithm for the maximum induced planar subgraph problem. (English) Zbl 1346.05283

Demetrescu, Camil (ed.) et al., Algorithms – ESA 2011. 19th annual European symposium, Saarbrücken, Germany, September 5–9, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-23718-8/pbk). Lecture Notes in Computer Science 6942, 287-298 (2011).
Summary: We prove that in an \(n\)-vertex graph, an induced planar subgraph of maximum size can be found in time \(O(1.7347^{n })\). This is the first algorithm breaking the trivial \(2^{n } n ^{O(1)}\) bound of the brute-force search algorithm for the Maximum Induced Planar Subgraph problem.
For the entire collection see [Zbl 1222.68007].

MSC:

05C85 Graph algorithms (graph-theoretic aspects)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI