Partial vs. Complete Domination: t-Dominating Set

DOI10.1007/978-3-540-69507-3_31MaRDI QIDQ5448787zbMATH OpenOpenAlexFDO

Authors 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

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

Recommendations

• Parameterized Algorithms for Generalized Domination
• Parameterized Complexity of Generalized Domination Problems
• Parameterized complexity of generalized domination problems
• New parameterized algorithms for the edge dominating set problem
• Parameterized Complexity for Domination Problems on Degenerate Graphs

Cited in

(28)

• The complexity of probabilistic lobbying
• Subexponential algorithms for partial cover problems
• On the parameterized complexity of the expected coverage problem
• Parallel algorithm for minimum partial dominating set in unit disk graph
• Inclusion/exclusion meets measure and conquer
• Parallel algorithms for minimum general partial dominating set and maximum budgeted dominating set in unit disk graph
• An FPT-algorithm for modifying a graph of bounded treewidth to decrease the size of its dominating set using minimum modification
• Hardness of r-dominating set on graphs of diameter (r + 1)
• Inclusion/Exclusion Branching for Partial Dominating Set and Set Splitting
• Parameterized Algorithms for Partial Vertex Covers in Bipartite Graphs
• On the Parameterized Complexity of the Expected Coverage Problem
• On the fixed-parameter tractability of the partial vertex cover problem with a matching constraint in edge-weighted bipartite graphs
• Approximating partially bounded degree deletion on directed graphs
• Parameterized Complexity for Domination Problems on Degenerate Graphs
• Improved Upper Bounds for Partial Vertex Cover
• Partial vertex cover and budgeted maximum coverage in bipartite graphs
• Parameterized Algorithms for Generalized Domination
• SOFSEM 2006: Theory and Practice of Computer Science
• Further Exploiting c-Closure for FPT Algorithms and Kernels for Domination Problems
• Grouped domination parameterized by vertex cover, twin cover, and beyond
• On the partial vertex cover problem in bipartite graphs -- a parameterized perspective
• Profit parameterizations of \textsc{Dominating Set}
• Implicit branching and parameterized partial cover problems
• Solving a family of multivariate optimization and decision problems on classes of bounded expansion
• Temporal reachability dominating sets: contagion in temporal graphs
• Partial domination in some geometric intersection graphs
• Solving partial dominating set and related problems using twin-width
• Representative families: a unified tradeoff-based approach

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

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