DAG-Width and Circumference of Digraphs

DOI10.1002/jgt.21894zbMath1339.05156arXiv1502.03241OpenAlexW2964220882MaRDI QIDQ2811203

Tilde My Larsen, Jörgen Bang-Jensen

Publication date: 10 June 2016

Published in: Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

polynomial algorithmDAG-width\(k\)-linkage problembounded cycle lengthcops-and-robbers game

Mathematics Subject Classification ID

Distance in graphs (05C12) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items (2)

Parameterized algorithms for generalizations of directed feedback vertex set ⋮ Digraphs of Bounded Width

Cites Work

• The dag-width of directed graphs
• Finding a subdivision of a digraph
• Disjoint paths in tournaments
• Digraph measures: Kelly decompositions, games, and orderings
• The directed subgraph homeomorphism problem
• Graph searching and a min-max theorem for tree-width
• Directed tree-width
• Graph minors. XIII: The disjoint paths problem
• On strongly connected digraphs with bounded cycle length
• Are There Any Good Digraph Width Measures?
• A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
• Tree-width and circumference of graphs
• Digraphs

This page was built for publication: DAG-Width and Circumference of Digraphs