Edge decompositions of multigraphs into multi-2-paths

• Autorzy: Kratochvil J. , Lonc Z. , Meszka M. , Skupień Z.
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

edge decomposition; multigraph; multipath; path; time complexity

• Wydawca: AGH University of Science and Technology Press
• Czasopismo: Opuscula Mathematica
• Rocznik: 2004
• Tom: Vol. 24, no. 1
• Strony: 97--102
• Opis fizyczny: Bibliogr. 18 poz.

Twórcy

autor

Kratochvil J.

• Charles University, Department of Applied Mathematics, Prague, Czech Republic

autor

Lonc Z.

• Warsaw University of Technology Faculty of Mathematics and Information Sciences pl. Politechniki 1, 00-661 Warsaw, Poland

autor

Meszka M.

• AGH University of Science and Technology Faculty of Applied Mathematics al. Mickiewicza 30, 30-059 Cracow, Poland

autor

Skupień Z.

• AGH University of Science and Technology Faculty of Applied Mathematics al. Mickiewicza 30, 30-059 Cracow, Poland

Bibliografia

• [1] Asratian A., Oksimets N.: Pk+i-decompositions of eulerian graphs: complexity and some solvable cases, [in:] Broersma H. J. et al, eds., Sci. Program 2nd Cologne Twente Workshop on Graphs and Combinatorial Optimization, May 2003, Univ. Twente, Enschede, The Netherlands, 9-13.
• [2] Bryś K., Lone Z.: A complete solution of the Holyer problem, [in:] Faigle U., Hoede C, eds., Ąth Twente Workshop on Graphs and Combinatorial Optimization, June 1995, Fac. Appl. Math. Univ. Twente, Enschede, The Netherlands.
• [3] Bryś K., Lone Z.: Polynomial cases of graph decomposition: a complete solution of Holyer's problem, submitted.
• [4] Bosak J.: Decompositions of Graphs. Dordrecht; Kluwer, Bratislava, Veda 1990, Bratislava, Veda 1986 (Slovak).
• [5] Białostocki A., Roditty I.: "iKi-decomposition of a graph. Acta Math. Hungar. 40 (1982), 201-208.
• [6] Caro Y., Schonheim J.: Decompositions of trees into isomorphic subtrees. Ars Combin. 9 (1980), 119-130.
• [7] Dor D., Tarsi M.: Graph decomposition is NPC - A complete proof of Holyer's conjecture, [in:] Proceedings of the 2Ąth Annual ACM Symposium on Theory of Computing (1992), 252-263.
• [8] Holyer I.: The NP-completeness of some edge-partition problems. SIAM J. Corn-put. 10 (1981), 713-717.
• [9] Ivanco J., Meszka M., Skupień Z.: Decomposition of multigraphs into isomorphic graphs with two edges. Ars Combin. 51 (1999), 105-112.
• [10] Ivanco J., Meszka M., Skupień Z.: Decompositions of multigraphs into parts with two edges, [in:] Harant J., Voigt M., Schiermeyer I., eds., Discuss. Math. Graph Theory 22 (2002), 113-121.
• [11] Javors'kii E. B.: Representations of oriented graphs and ^-transformations [Russian], [in:] Sarkovskij A. N., ed., Theoretical and Applied Problems of Differential Equations and Algebra. Kiev, Nauk. Dumka 1978, 247-250 (Russian).
• [12] Jungerman M.: A characterization of upper embeddable graphs. Trans. Amer. Math. Soc. 241 (1978), 401-406.
• [13] Kotzig A.: From the theory of finite regular graphs of degree three and four. Ćasopis Pestov. Mat. 82 (1957), 76-92 (Slovak).
• [14] Kouider M., Maheo M., Bryś K., Lone Z.: Decomposition of multigraphs. Discuss. Math. Graph Theory 18 (1998), 225-232.
• [15] Lone Z., Meszka M., Skupień Z.: Edge decompositions of multigraphs into 3--matchings. Graphs Combin., to appear.
• [16] Priesler M.: Multistar Decomposition of Multigraphs. PhD thesis, Tel Aviv University, April 2002.
• [17] Skupień Z.: Problem [on complexity of P(2,1)-decompositions], presented at Czecho-Slovak Conl. Graphs'96, held at Velke Karlovice, 10-14.06.1996.
• [18] Skupień Z.: Problem 270 [on 2-edge-decomposable multigraphs]. Discrete Math. 164 (1997), 320-321.