Finding coherent cyclic orders in strong digraphs |
| |
Authors: | Satoru Iwata Takuro Matsuda |
| |
Institution: | (1) Research Institute for Mathematical Sciences, Kyoto University, Kyoto 606-8502, Japan;(2) Fujitsu, Shinkamata Ohta-ku, Tokyo 144-8588, Japan |
| |
Abstract: | A cyclic order in the vertex set of a digraph is said to be coherent if any arc is contained in a directed cycle whose winding
number is one. This notion plays a key role in the proof by Bessy and Thomassé (2004) of a conjecture of Gallai (1964) on
covering the vertex set by directed cycles. This paper presents an efficient algorithm for finding a coherent cyclic order
in a strongly connected digraph, based on a theorem of Knuth (1974). With the aid of ear decomposition, the algorithm runs
in O(nm) time, where n is the number of vertices and m is the number of arcs. This is as fast as testing if a given cyclic order is coherent. |
| |
Keywords: | 05C20 90C27 |
本文献已被 SpringerLink 等数据库收录! |
|