Subexponential fixed-parameter algorithms for partial vector domination

DOI10.1007/978-3-319-09174-7_25MaRDI QIDQ3195339zbMATH OpenOpenAlexFDO

Authors Toshimasa Ishii, Hirotaka Ono, Yushi Uno

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

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph algorithms (graph-theoretic aspects) (05C85) Parameterized complexity, tractability and kernelization (68Q27) Programming involving graphs or networks (90C35)

Recommendations

• Subexponential fixed-parameter algorithms for partial vector domination
• (Total) vector domination for graphs with bounded branchwidth
• (Total) vector domination for graphs with bounded branchwidth
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs

Cites work

• (Total) vector domination for graphs with bounded branchwidth
• Bidimensionality: new connections between FPT algorithms and PTASs
• Call routing and the ratcatcher
• Constructive linear time algorithms for branchwidth
• Dominating Sets in Planar Graphs: Branch-Width and Exponential Speed-Up
• Dynamic Programming and Fast Matrix Multiplication
• Fixed-parameter algorithms for ( k , r )-center in planar graphs and map graphs
• Graph minors. X: Obstructions to tree-decomposition
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• scientific article; zbMATH DE number 1095171 (Why is no real title available?)
• scientific article; zbMATH DE number 1095172 (Why is no real title available?)
• scientific article; zbMATH DE number 1792607 (Why is no real title available?)
• Implicit branching and parameterized partial cover problems
• Latency-bounded target set selection in social networks
• On bounded-degree vertex deletion parameterized by treewidth
• On Dominating Sets and Independent Sets of Graphs
• On the approximability and exact algorithms for vector domination and related problems in graphs
• On the Relationship Between Clique-Width and Treewidth
• Parameterized Algorithms for Generalized Domination
• Subexponential algorithms for partial cover problems
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs

Cited in

(6)

• Subexponential fixed-parameter algorithms for partial vector domination
• On the approximability and exact algorithms for vector domination and related problems in graphs
• Vector domination in split-indifference graphs
• (Total) vector domination for graphs with bounded branchwidth
• Hardness, approximability, and exact algorithms for vector domination and total vector domination in graphs
• (Total) vector domination for graphs with bounded branchwidth

This page was built for publication: Subexponential fixed-parameter algorithms for partial vector domination

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