Kernels in planar digraphs

DOI10.1016/J.JCSS.2005.02.003MaRDI QIDQ2485283zbMATH OpenOpenAlexFDO

Authors G. Gutin, Chuan-Min Lee, A. 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

zbMATH Keywords

KernelsFixed-parameter complexityPlanar digraphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Recommendations

• A Polyhedral Description of Kernels
• Kernels in a special class of digraphs
• Strong kernel in certain oriented networks
• scientific article; zbMATH DE number 4212085
• Almost all digraphs have a kernel

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1341905 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2079336 (Why is no real title available?)
• scientific article; zbMATH DE number 1929955 (Why is no real title available?)
• scientific article; zbMATH DE number 3803484 (Why is no real title available?)
• scientific article; zbMATH DE number 1834643 (Why is no real title available?)
• scientific article; zbMATH DE number 806748 (Why is no real title available?)
• scientific article; zbMATH DE number 3106184 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A classification of locally semicomplete digraphs
• Advice classes of parametrized tractability
• Call routing and the ratcatcher
• Combinatorial game theory foundations applied to digraph kernels
• Counterexamples of the 0-1 Law for Fragments of Existential Second-Order Logic: an Overview
• Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
• Graph minors. X: Obstructions to tree-decomposition
• Mathematical Foundations of Computer Science 2004
• On the existence of subexponential parameterized algorithms
• Planar kernel and Grundy with d 3, dout 2, din 2 are NP- complete
• Polynomial-time data reduction for dominating set
• Recent problems and results about kernels in directed graphs
• Treewidth. Computations and approximations

Cited in

(12)

• Partitioning vertices into in- and out-dominating sets in digraphs
• Almost all digraphs have a kernel
• Counting kernels in directed graphs with arbitrary orientations
• Linearity of grid minors in treewidth with applications through bidimensionality
• Finding kernels or solving SAT
• scientific article; zbMATH DE number 6194066 (Why is no real title available?)
• Algorithmic graph minor theory: Improved grid minor bounds and Wagner's contraction
• Kernels in digraphs with covering number at most 3
• Parameterized complexity: the main ideas and connections to practical computing
• Subexponential parameterized algorithms
• Kernels in weighted digraphs
• Polynomial algorithms for kernels in comparability, permutation and P₄-free graphs

This page was built for publication: Kernels in planar digraphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2485283)