Partitioning graphs into two trees

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.

Elmentve itt :
Bibliográfiai részletek
Szerzők: Pferschy Ulrich
Woeginger Gerhard J.
Yao En-Yu
Dokumentumtípus: Cikk
Megjelent: 1994
Sorozat:Acta cybernetica 11 No. 3
Kulcsszavak:Számítástechnika, Kibernetika
Tárgyszavak:
Online Access:http://acta.bibl.u-szeged.hu/12531
Leíró adatok
Tartalmi kivonat: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.
Terjedelem/Fizikai jellemzők:233-240
ISSN:0324-721X