Tytuł artykułu
Autorzy
Wybrane pełne teksty z tego czasopisma
Identyfikatory
Warianty tytułu
Języki publikacji
Abstrakty
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
Czasopismo
Rocznik
Tom
Strony
97--102
Opis fizyczny
Bibliogr. 18 poz.
Twórcy
autor
- Charles University, Department of Applied Mathematics, Prague, Czech Republic
autor
- Warsaw University of Technology Faculty of Mathematics and Information Sciences pl. Politechniki 1, 00-661 Warsaw, Poland
autor
- AGH University of Science and Technology Faculty of Applied Mathematics al. Mickiewicza 30, 30-059 Cracow, Poland
autor
- 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.
Typ dokumentu
Bibliografia
Identyfikator YADDA
bwmeta1.element.baztech-article-AGH4-0005-0068