Algorithms – ESA 2004
From MaRDI portal
Publication:5464578
DOI10.1007/b100428zbMath1111.68782OpenAlexW2483610301MaRDI QIDQ5464578
Janka Chlebíková, Miroslav Chlebík
Publication date: 18 August 2005
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/b100428
Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Related Items
A polynomial-time approximation to a minimum dominating set in a graph, The \(k\)-hop connected dominating set problem: approximation and hardness, Parameterized complexity and inapproximability of dominating set problem in chordal and near chordal graphs, Approximability results for the maximum and minimum maximal induced matching problems, The hub number of a graph, Complexity and approximation results for the connected vertex cover problem in graphs and hypergraphs, On the approximability of positive influence dominating set in social networks, The complexity of dissociation set problems in graphs, New kernels for several problems on planar graphs, Domination in Geometric Intersection Graphs, On the approximability of the maximum agreement subtree and maximum compatible tree problems, The parameterized complexity of the induced matching problem, On the complexity of independent dominating set with obligations in graphs