Recognizing digraphs of Kelly-width 2

DOI10.1016/J.DAM.2009.09.018MaRDI QIDQ972333zbMATH OpenOpenAlexFDO

Authors Daniel Meister, Jan Arne Telle, Martin Vatshelle

Publication date 25 May 2010

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.dam.2009.09.018

zbMATH Keywords

characterizationrecognitionKelly-widthdigraph width parameter

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85)

Recommendations

• Characterization and Recognition of Digraphs of Bounded Kelly-width
• Digraphs of bounded elimination width
• Digraph measures: Kelly decompositions, games, and orderings
• Digraph measures: Kelly decompositions, games, and orderings
• On digraph width measures in parameterized algorithmics

Cites work

• All structured programs have small tree width and good register allocation
• DAG-Width and Parity Games
• DAG-width
• Digraph measures: Kelly decompositions, games, and orderings
• Directed tree-width
• Forbidden minors characterization of partial 3-trees
• Fugitive-search games on graphs and related parameters
• Mathematical Foundations of Computer Science 2005
• Treewidth: Characterizations, Applications, and Computations

Cited in

(6)

• Chordal digraphs
• Directed width parameters and circumference of digraphs
• Forbidden directed minors and Kelly-width
• Digraphs of bounded width
• Characterization and Recognition of Digraphs of Bounded Kelly-width
• Digraphs of bounded elimination width

This page was built for publication: Recognizing digraphs of Kelly-width 2

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