Partitioning graphs into two trees

Pferschy Ulrich and Woeginger Gerhard J. and Yao En-Yu: Partitioning graphs into two trees. In: Acta cybernetica, (11) 3. pp. 233-240. (1994)

[thumbnail of cybernetica_011_numb_003_233-240.pdf]
Cikk, tanulmány, mű

Download (642kB) | Preview


We investigate the problem of partitioning the edges of a graph into two trees of equal size. We prove that this problem is NP-complete in general, but can be solved in polynomial time on series-parallel graphs.

Item Type: Article
Journal or Publication Title: Acta cybernetica
Date: 1994
Volume: 11
Number: 3
ISSN: 0324-721X
Page Range: pp. 233-240
Language: English
Place of Publication: Szeged
Related URLs:
Uncontrolled Keywords: Számítástechnika, Kibernetika
Additional Information: Bibliogr.: 240. p. ; összefoglalás angol nyelven
Subjects: 01. Natural sciences
01. Natural sciences > 01.02. Computer and information sciences
Date Deposited: 2016. Oct. 15. 12:26
Last Modified: 2022. Jun. 13. 11:51

Actions (login required)

View Item View Item