The 2-linkage problem for acyclic digraphs

DOI10.1016/S0012-365X(85)80022-4MaRDI QIDQ1057282zbMATH OpenOpenAlexFDO

Authors Carsten Thomassen

Publication date 1985

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0012-365x(85)80022-4

zbMATH Keywords

acyclic digraphdirected pathsdistinct cyclesshortest cycles

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Planar graphs; geometric and topological aspects of graph theory (05C10) Paths and cycles (05C38)

Recommendations

• scientific article; zbMATH DE number 4085689
• On digraphs with no two disjoint directed cycles
• Disjoint paths in acyclic digraphs
• On the problem of finding disjoint cycles and dicycles in a digraph
• The directed 2-linkage problem with length constraints

Cites work

• scientific article; zbMATH DE number 3613081 (Why is no real title available?)
• scientific article; zbMATH DE number 3630786 (Why is no real title available?)
• scientific article; zbMATH DE number 3204690 (Why is no real title available?)
• 2-linked graphs
• Cycles in digraphs– a survey
• Disjoint cycles in digraphs
• Disjoint paths in graphs
• Efficient Planarity Testing
• On independent circuits of a digraph
• On the number of cycles possible in digraphs with large girth
• Planarity and duality of finite and infinite graphs
• The directed subgraph homeomorphism problem

Cited in

(21)

• A note on short cycles in digraphs
• Vertex-disjoint directed and undirected cycles in general digraphs
• On digraphs with no two disjoint directed cycles
• Finding a homotopy base for directed paths in an acyclic graph
• DAG-width and circumference of digraphs
• Openly disjoint circuits through a vertex in regular digraphs
• Linkages in locally semicomplete digraphs and quasi-transitive digraphs
• The Hoàng-Reed conjecture for \(\delta ^{+}=3\)
• Nearly sign-nonsingular matrices
• scientific article; zbMATH DE number 4085689 (Why is no real title available?)
• Sign-nonsingular matrices and even cycles in directed graphs
• Thomassen's theorem on the two-linkage problem in acyclic digraphs: a shorter proof
• On the problem of finding disjoint cycles and dicycles in a digraph
• Characterization of even directed graphs
• Linear time algorithms for two disjoint paths problems on directed acyclic graphs
• Arc-disjoint directed and undirected cycles in digraphs
• Tournaments and Semicomplete Digraphs
• Existence of openly disjoint circuits through a vertex
• Oriented cycles in digraphs of large outdegree
• Hoàng-Reed conjecture holds for tournaments
• When all directed cycles have length three

This page was built for publication: The 2-linkage problem for acyclic digraphs

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