Recognizing digraphs of Kelly-width 2

DOI10.1016/J.DAM.2009.09.018zbMATH Open1216.05160OpenAlexW2024884639MaRDI QIDQ972333FDOQ972333

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

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

zbMATH Keywords

characterizationrecognitionKelly-widthdigraph width parameter

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (6)

• Digraphs of Bounded Width
• Chordal digraphs
• Directed width parameters and circumference of digraphs
• Forbidden directed minors and Kelly-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)