Edge decompositions of multigraphs into multi-2-paths

Jan Kratochvı́l, Zbigniew Lonc, Mariusz Meszka, Zdzisław SkupieńSHILAP 2004

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.
BibTeX
@inproceedings{kratochvl2004edge,
  author = {Jan Kratochvı́l and Zbigniew Lonc and Mariusz Meszka and Zdzisław Skupień},
  title = {{Edge decompositions of multigraphs into multi-2-paths}},
  booktitle = {SHILAP},
  year = {2004},
}

Loading related content...

Figure