Kernels in planar digraphs
From MaRDI portal
Publication:2485283
DOI10.1016/j.jcss.2005.02.003zbMath1170.68547OpenAlexW2077761942MaRDI QIDQ2485283
Gregory Gutin, Chuan-Min Lee, Anders Yeo, Ton Kloks
Publication date: 3 August 2005
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2005.02.003
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Finding kernels or solving SAT ⋮ Partitioning vertices into in- and out-dominating sets in digraphs ⋮ Subexponential parameterized algorithms ⋮ Linearity of grid minors in treewidth with applications through bidimensionality ⋮ Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction ⋮ Parameterized Complexity
Cites Work
- Advice classes of parametrized tractability
- Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
- Graph minors. X: Obstructions to tree-decomposition
- Call routing and the ratcatcher
- Treewidth. Computations and approximations
- A classification of locally semicomplete digraphs
- Combinatorial game theory foundations applied to digraph kernels
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- On the existence of subexponential parameterized algorithms
- Recent problems and results about kernels in directed graphs
- Polynomial-time data reduction for dominating set
- Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
- Mathematical Foundations of Computer Science 2004
- A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
