A bounded search tree algorithm for parameterized face cover

DOI10.1016/J.JDA.2008.07.004MaRDI QIDQ1002098zbMATH OpenOpenAlexFDO

Authors Faisal N. Abu-Khzam, Henning Fernau, Michael A. Langston

Publication date 23 February 2009

Published in Journal of Discrete Algorithms (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jda.2008.07.004

zbMATH Keywords

fixed-parameter algorithmsplane graphsface coverplanar red-blue dominating set

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Search theory (90B40)

Recommendations

• Parameterized and Exact Computation
• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Planar Feedback Vertex Set and Face Cover: Combinatorial Bounds and Subexponential Algorithms
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• scientific article; zbMATH DE number 1953101

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• A refined search tree technique for dominating set on planar graphs
• A top-down approach to search-trees: Improved algorithmics for 3-hitting set
• An efficient fixed-parameter algorithm for 3-hitting set
• Automata, Languages and Programming
• Deeply asymmetric planar graphs
• Exact algorithms for finding minimum transversals in rank-3 hypergraphs
• Mathematical Foundations of Computer Science 2004
• On the Complexity of Covering Vertices by Faces in a Planar Graph
• Parameterized and Exact Computation
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• Refined memorization for vertex cover
• Two-Layer Planarization: Improving on Parameterized Algorithmics

Cited in

(4)

• Planar feedback vertex set and face cover: combinatorial bounds and subexponential algorithms
• Planarizing graphs and their drawings by vertex splitting
• scientific article; zbMATH DE number 1953101 (Why is no real title available?)
• Parameterized and Exact Computation

This page was built for publication: A bounded search tree algorithm for parameterized face cover

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