Opuscula Math. 24, no. 1 (2004), 97-102
Edge decompositions of multigraphs into multi-2-paths
Jan Kratochvil
Zbigniew Lonc
Mariusz Meszka
Zdzisław Skupień
Abstract.
We establish the computational time complexity of the existence problem of a decomposition of an instance multigraph into isomorphic 3-vertex paths with multiple edges. If the two edge multiplicities are distinct, the problem is NPC; if mutually equal then polynomial.
Keywords:
edge decomposition, multigraph, multipath, path, time complexity.
Mathematics Subject Classification:
05C38, 05C85.
About the authors ▼
Jan Kratochvil
Charles University, Department of Applied Mathematics, Prague, Czech Republic
Zbigniew Lonc
Warsaw University of Technology, Faculty of Mathematics and Information Sciences, pl. Politechniki 1, 00-661 Warsaw, Poland
Mariusz Meszka
AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland
Zdzisław Skupień
AGH University of Science and Technology, Faculty of Applied Mathematics, al. Mickiewicza 30, 30-059 Cracow, Poland
About the article ▼
Received: 2004-03-31.
Cite this article as ▼
Jan Kratochvil, Zbigniew Lonc, Mariusz Meszka, Zdzisław Skupień, Edge decompositions of multigraphs into multi-2-paths, Opuscula Math. 24, no. 1 (2004), 97-102,
http://dx.doi.org/10.7494/OpMath.2004.24.1.97.
Download this article's citation as: