Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs

DOI10.1007/s10878-010-9317-7zbMath1236.90136OpenAlexW2020877234WikidataQ43088519 ScholiaQ43088519MaRDI QIDQ411223

Yinglei Song, Chunmei Liu

Publication date: 4 April 2012

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

Full work available at URL: https://europepmc.org/articles/pmc3713774

zbMATH Keywords

dominating setchordal graphsindependent dominating setparameterized complexity

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (6)

Perfect domination and small cycles ⋮ On finding the longest antisymmetric path in directed acyclic graphs ⋮ Peptide sequencing via graph path decomposition ⋮ Secure total domination in graphs: bounds and complexity ⋮ An improved exact algorithm for minimum dominating set in chordal graphs ⋮ On the induced matching problem in Hamiltonian bipartite graphs

Cites Work

• Unnamed Item
• Approximating the minimum maximal independence number
• Parameterized dominating set problem in chordal graphs: Complexity and lower bound
• On the inapproximability of independent domination in \(2P_3\)-free perfect graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Independent domination in chordal graphs
• Approximation algorithms for combinatorial problems
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• Vertex Cover: Further Observations and Further Improvements
• Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size
• The importance of being biased
• Linear FPT reductions and computational lower bounds
• Polynomial-time data reduction for dominating set
• Linear Kernel for Planar Connected Dominating Set
• Approximation algorithms for NP-complete problems on planar graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Algorithms – ESA 2004

This page was built for publication: Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs