On directed covering and domination problems

DOI10.4230/LIPICS.ISAAC.2017.45MaRDI QIDQ5136265zbMATHOpenAlexFDO

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

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)

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

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• 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 Sets in Graphs
• Finding Hamiltonian circuits in quasi-adjoint graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• 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
• edge dominating set: Efficient Enumeration-Based Exact Algorithms

Cited in

(4)

• 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
• On directed covering and domination problems

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)