On directed covering and domination problems

DOI10.4230/LIPICS.ISAAC.2017.45MaRDI QIDQ5136265zbMATH OpenOpenAlexFDO

Authors Tesshu Hanaka, N. Nishimura, Hirotaka Ono

Publication date 25 November 2020

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2017/8246/pdf/LIPIcs-ISAAC-2017-45.pdf/

zbMATH Keywords

directed graphdominating setedge dominating setfixed-parameter algorithmsvertex cover

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)

Recommendations

• On directed covering and domination problems
• New results on directed edge dominating set
• Algorithms – ESA 2004
• On the complexity of \textsc{broadcast domination} and \textsc{Multipacking} in digraphs
• On the complexity of broadcast domination and multipacking in digraphs

Cites work

• A c^k n 5-approximation algorithm for treewidth
• Analytical approach to parallel repetition
• Approximation hardness of dominating set problems in bounded degree graphs
• Digraph width measures in parameterized algorithmics
• Directed nowhere dense classes of graphs
• Directed tree-width
• Domination problems in nowhere-dense classes of graphs
• edge dominating set: Efficient Enumeration-Based Exact Algorithms
• Edge Dominating Sets in Graphs
• Finding Hamiltonian circuits in quasi-adjoint graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• Kernelization and Sparseness: the case of Dominating Set
• Nondeterminism within $P^ * $
• On some properties of DNA graphs
• Parameterized complexity of coloring problems: treewidth versus vertex cover
• Some properties of line digraphs
• The dag-width of directed graphs
• The edge Hamiltonian path problem is NP-complete

Cited in

(4)

• On directed covering and domination problems
• How to catch a lion in the desert: on the solution of the coverage directed generation (CDG) problem
• New results on directed edge dominating set
• New Results on Directed Edge Dominating Set

This page was built for publication: On directed covering and domination problems

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