On directed covering and domination problems
From MaRDI portal
Publication:1735678
DOI10.1016/j.dam.2018.12.012zbMath1407.05194MaRDI QIDQ1735678
Tesshu Hanaka, Naomi Nishimura, Hirotaka Ono
Publication date: 28 March 2019
Published in: Discrete Applied Mathematics (Search for Journal in Brave)
Full work available at URL: https://drops.dagstuhl.de/opus/volltexte/2017/8246/
05C70: Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C85: Graph algorithms (graph-theoretic aspects)
05C69: Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C20: Directed graphs (digraphs), tournaments
Related Items
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
- Treewidth. Computations and approximations
- Face covers and the genus problem for apex graphs
- 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
- k-cyclic Orientations of Graphs
- edge dominating set: Efficient Enumeration-Based Exact Algorithms
- Edge Dominating Sets in Graphs
- Planar Formulae and Their Uses
- Nondeterminism within $P^ * $
- Kernelization and Sparseness: the case of Dominating Set
- Fixed-Parameter Tractability and Completeness I: Basic Results
- Analytical approach to parallel repetition
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- Parameterized Algorithms
