Help please in DAG minimum path cover

Правка en1, от Pepe.Chess, 2015-08-28 21:48:12

Hello

I need Help please in this graph problem

I think you all know the minimum path cover problem in a DAG

You are given a DAG and you have to compose it into K paths so that every vertex must belong to exactly one path

So you have to find a solution where K is minimum

This can be solved by maximum matching.

But what if the vertex can belong to more than one path in the composition ???

For further understanding ... let's imagine this DAG

1->2

2->3

4->2

2->5

The standard covering will give us 3 as a result (1->2->3 , 4 , 5)

But in this version the answer would be 2 (1->2->3 , 4->2->5)

Does anyone have any idea?

Thanks in advance

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский Pepe.Chess 2015-08-28 21:48:12 718 Initial revision (published)