On Directed Covering and Domination Problems

DOI10.4230/LIPIcs.ISAAC.2017.45zbMath1457.05088OpenAlexW2783253555MaRDI QIDQ5136265

Hirotaka Ono, Tesshu Hanaka, Naomi Nishimura

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 setvertex coverfixed-parameter algorithmsedge dominating set

Mathematics Subject Classification ID

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

Related Items (1)

New Results on Directed Edge Dominating Set

Cites Work

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

This page was built for publication: On Directed Covering and Domination Problems