On directed covering and domination problems

DOI10.4230/LIPICS.ISAAC.2017.45zbMATH Open1457.05088OpenAlexW2783253555MaRDI QIDQ5136265FDOQ5136265

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/

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

zbMATH Keywords

dominating setfixed-parameter algorithmsdirected graphvertex coveredge dominating set

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) 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) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

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

Cited In (3)

• 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

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)