On digraphs with no two disjoint directed cycles |
| |
Authors: | C Thomassen |
| |
Institution: | (1) Math. Inst., The Technical University of Denmark, DK-2800 Lyngby, Denmark |
| |
Abstract: | We obtain a result on configurations in 2-connected digraphs with no two disjoint dicycles. We derive various consequences,
for example a short proof of the characterization of the minimal digraphs having no vertex meeting all dicycles and a polynomially
bounded algorithm for finding a dicycle through any pair of prescribed arcs in a digraph with no two disjoint dicycles, a
problem which is NP-complete for digraphs in general. |
| |
Keywords: | 05 C 20 05 C 38 |
本文献已被 SpringerLink 等数据库收录! |
|