zbMATH — the first resource for mathematics

Finding complementary cycles in locally semicomplete digraphs. (English) Zbl 1055.05086
Summary: It is well known that the problem of deciding whether a given digraph has a \(k\)-cycle factor for some constant \(k\) (i.e. a collection of \(k\) disjoint cycles that cover all vertices of the digraph) is \(\mathcal{NP}\)-complete as this is a generalization of the Hamilton cycle problem. In this paper, we show that for the class of locally semicomplete digraphs the existence of a 2-cycle factor can be decided, and a 2-cycle factor found if it exists, in time \(\mathcal O(n^3)\), where \(n\) is the order of the digraph.

05C38 Paths and cycles
05C20 Directed graphs (digraphs), tournaments
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI
[1] Bang-Jensen, J., Locally semicomplete digraphsa generalization of tournaments, J. graph theory, 14, 371-390, (1990) · Zbl 0703.05026
[2] Bang-Jensen, J.; Gutin, G., Digraphstheory, algorithms and applications, (2001), Springer New York
[3] J. Bang-Jensen, M.H. Nielsen, Minimum cycle factors in quasi-transitive digraphs, submitted for publication. · Zbl 1134.90045
[4] Guo, Y.; Volkmann, L., On complementary cycles in locally semicomplete digraphs, Discrete math., 135, 121-127, (1994) · Zbl 0816.05036
[5] H. Li, J. Shu, The partition of a strong tournament, Rapport de Recherce No. 1306, Laboratoire de Recherche en Informatique, Université de Paris Sud, 2002. · Zbl 1069.05037
[6] Reid, K.B., Two complementary circuits in two-connected tournaments, (), 321-334 · Zbl 0573.05031
[7] Song, Z.M., Complementary cycles of all lengths in tournaments, J. combin. theory ser. B, 57, 18-25, (1993) · Zbl 0723.05062
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.