Subexponential Fixed-Parameter Algorithms for Partial Vector Domination

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

Mathematics Subject Classification ID

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

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Subexponential Fixed-Parameter Algorithms for Partial Vector Domination