Partial vs. Complete Domination: t-Dominating Set

DOI10.1007/978-3-540-69507-3_31zbMath1131.68488OpenAlexW1799048485MaRDI QIDQ5448787

Joachim Kneis, Daniel Mölle, Peter Rossmanith

Publication date: 7 March 2008

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-540-69507-3_31

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Randomized algorithms (68W20)

Related Items (20)

Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs ⋮ An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification ⋮ On the Parameterized Complexity of the Expected Coverage Problem ⋮ On the parameterized complexity of the expected coverage problem ⋮ Parameterized Complexity for Domination Problems on Degenerate Graphs ⋮ Improved Upper Bounds for Partial Vertex Cover ⋮ Parallel algorithm for minimum partial dominating set in unit disk graph ⋮ The complexity of probabilistic lobbying ⋮ On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs ⋮ Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph ⋮ Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems ⋮ Representative families: a unified tradeoff-based approach ⋮ On the partial vertex cover problem in bipartite graphs -- a parameterized perspective ⋮ Subexponential algorithms for partial cover problems ⋮ Implicit branching and parameterized partial cover problems ⋮ Parameterized and approximation complexity of \textsc{Partial VC Dimension} ⋮ Inclusion/exclusion meets measure and conquer ⋮ Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting ⋮ Partial Vertex Cover and Budgeted Maximum Coverage in Bipartite Graphs ⋮ Approximating Partially Bounded Degree Deletion on Directed Graphs

This page was built for publication: Partial vs. Complete Domination: t-Dominating Set