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

DOI10.1007/s10878-008-9141-5zbMath1170.90508OpenAlexW2039933854MaRDI QIDQ839675

Yinglei Song, Chunmei Liu

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

lower bounddominating setchordal graphsinterval graphsparameterized complexity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items

Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs ⋮ On finding the longest antisymmetric path in directed acyclic graphs ⋮ Peptide sequencing via graph path decomposition ⋮ On the induced matching problem in Hamiltonian bipartite graphs

Cites Work

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