首页 | 本学科首页   官方微博 | 高级检索  
     检索      


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 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号