Directed width parameters and circumference of digraphs

DOI10.1016/J.TCS.2016.10.010zbMATH Open1357.05052arXiv1401.2662OpenAlexW2407066649MaRDI QIDQ730003FDOQ730003

Authors: Shiva Kintali 

Publication date: 23 December 2016

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

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

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)

Cites Work

• Introduction to algorithms
• Directed tree-width
• The dag-width of directed graphs
• Title not available (Why is that?)
• Digraph measures: Kelly decompositions, games, and orderings
• Sparsity. Graphs, structures, and algorithms
• DAG-Width and Parity Games
• DAG-width
• Tree-width and circumference of graphs
• Recognizing digraphs of Kelly-width 2
• Circumference and pathwidth of highly connected graphs

Cited In (2)

• A Menger-like property of tree-cut width
• Digraphs of bounded 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)