Parameterized dominating set problem in chordal graphs: Complexity and lower bound

DOI10.1007/S10878-008-9141-5zbMATH Open1170.90508OpenAlexW2039933854MaRDI QIDQ839675FDOQ839675

Authors Chunmei Liu, Yinglei Song

Publication date 2 September 2009

Published in Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s10878-008-9141-5

zbMATH Keywords

dominating setinterval graphslower boundchordal graphsparameterized complexity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Recommendations

• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Hardness of \(r\)-dominating set on graphs of diameter \((r + 1)\)
• Parameterized complexity in multiple-interval graphs: domination
• scientific article; zbMATH DE number 1929955
• Parameterized Complexity for Domination Problems on Degenerate Graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Characterization of Comparability Graphs and of Interval Graphs
• Dominating Sets in Chordal Graphs
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Geometric separation and exact solutions for the parameterized independent set problem on disk graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Graph minors. III. Planar tree-width
• Graph minors. IV: Tree-width and well-quasi-ordering
• Graph minors. V. Excluding a planar graph
• Linear FPT reductions and computational lower bounds
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• Parameterized Complexity of Independence and Domination on Geometric Graphs
• Polynomial-time data reduction for dominating set
• STACS 2005

Cited in

(8)

• The parallel solution of domination problems on chordal and strongly chordal graphs
• Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs
• Hardness of \(r\)-dominating set on graphs of diameter \((r + 1)\)
• Parameterized Complexity of the Sparsest k-Subgraph Problem in Chordal Graphs
• Parameterized algorithms for Steiner tree and (connected) dominating set on path graphs
• Peptide sequencing via graph path decomposition
• On the induced matching problem in Hamiltonian bipartite graphs
• On finding the longest antisymmetric path in directed acyclic graphs

This page was built for publication: Parameterized dominating set problem in chordal graphs: Complexity and lower bound

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