Subexponential fixed-parameter algorithms for partial vector domination
From MaRDI portal
Publication:1751177
DOI10.1016/j.disopt.2016.01.003zbMath1387.90265OpenAlexW2748129119MaRDI QIDQ1751177
Hirotaka Ono, Yushi Uno, Toshimasa Ishii
Publication date: 24 May 2018
Published in: Discrete Optimization (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.disopt.2016.01.003
fixed-parameter tractabilitybranchwidthapex-minor-free graphs(total) vector dominating setpartial dominating set
Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Parameterized complexity of generalized domination problems
- A linear kernel for planar red-blue dominating set
- Implicit branching and parameterized partial cover problems
- On bounded-degree vertex deletion parameterized by treewidth
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Which problems have strongly exponential complexity?
- On the existence of subexponential parameterized algorithms
- Subexponential algorithms for partial cover problems
- On the approximability and exact algorithms for vector domination and related problems in graphs
- Latency-bounded target set selection in social networks
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
- Hardness, Approximability, and Exact Algorithms for Vector Domination and Total Vector Domination in Graphs
- Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
- Constructive linear time algorithms for branchwidth
- On the total k-domination number of graphs
- On Dominating Sets and Independent Sets of Graphs
- On the Relationship Between Clique-Width and Treewidth
- (Total) Vector Domination for Graphs with Bounded Branchwidth
- Dynamic Programming and Fast Matrix Multiplication
- Parameterized Algorithms for Generalized Domination
This page was built for publication: Subexponential fixed-parameter algorithms for partial vector domination
