Opuscula Math. 24, no. 1 (2004), 97-102
Opuscula Mathematica
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.
- 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
- Received: 2004-03-31.
