TY  - JOUR
ID  - Kratochvil2004
LB  - Kratochvil2004
AU  - Kratochvil, Jan
AU  - Lonc, Zbigniew
AU  - Meszka, Mariusz
AU  - Skupień, Zdzisław
TI  - Edge decompositions of multigraphs into multi-2-paths
ST  - Edge decompositions of multigraphs into multi-2-paths
JO  - Opuscula Math.
JA  - Opuscula Math.
JF  - Opuscula Mathematica
PY  - 2004
VL  - 24
IS  - 1
SP  - 97
EP  - 102
DO  - http://dx.doi.org/10.7494/OpMath.2004.24.1.97
UR  - http://dx.doi.org/10.7494/OpMath.2004.24.1.97
AB  - 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.
KW  - edge decomposition
KW  - multigraph
KW  - multipath
KW  - path
KW  - time complexity
SN  - 1232-9274
ER  -