Subexponential Fixed-Parameter Algorithms for Partial Vector Domination
From MaRDI portal
Publication:3195339
DOI10.1007/978-3-319-09174-7_25zbMath1445.90111OpenAlexW419104854MaRDI QIDQ3195339
Yushi Uno, Toshimasa Ishii, Hirotaka Ono
Publication date: 16 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: http://hdl.handle.net/2115/71766
Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
- Subexponential algorithms for partial cover problems
- On the approximability and exact algorithms for vector domination and related problems in graphs
- 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 Dominating Sets and Independent Sets of Graphs
- On the Relationship Between Clique-Width and Treewidth
- Latency-Bounded Target Set Selection in Social Networks
- (Total) Vector Domination for Graphs with Bounded Branchwidth
- Dynamic Programming and Fast Matrix Multiplication
- Parameterized Algorithms for Generalized Domination