Directed width parameters and circumference of digraphs

DOI10.1016/J.TCS.2016.10.010MaRDI QIDQ730003zbMATH OpenOpenAlexFDO

Authors Shiva Kintali

Publication date 23 December 2016

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1401.2662

zbMATH Keywords

directed treewidthDAG-widtharboreal decompositionDAG-decompositionKelly decompositionKelly-width

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: We prove that the directed treewidth, DAG-width and Kelly-width of a digraph are bounded above by its circumference plus one.

Cites work

• scientific article; zbMATH DE number 2203240 (Why is no real title available?)
• Circumference and pathwidth of highly connected graphs
• DAG-Width and Parity Games
• DAG-width
• Digraph measures: Kelly decompositions, games, and orderings
• Directed tree-width
• Introduction to algorithms
• Recognizing digraphs of Kelly-width 2
• Sparsity. Graphs, structures, and algorithms
• The dag-width of directed graphs
• Tree-width and circumference of graphs

Cited in

(2)

• Digraphs of bounded width
• A Menger-like property of tree-cut width

This page was built for publication: Directed width parameters and circumference of digraphs

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