Re: minimum disjoint paths covering of a graph - algorithm needed


>> John Gabbriel:
> Ah, well that makes the problem hard.
> I think it is NP-Complete as Hamiltonian path problem can be reduced to
> this.
[...]

yes, u are right. i have spent some hours googling, and i have found that
for bipartite graphs it's NP-complete ...
there are only some special graph types where its polynomial-time or less.

for example : directed acyclic graphs, cographs, trees.

i also tried to find how to compute the number of minimum path cover (not
the solution, just the number of paths i need), but with no resoults :/

AFAIK it's not NP-complete,

thank you.
Marcin
zgadnij@xxxxxxxxx


.

Relevant Pages
Loading