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/
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)
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
