## 11419 - SAM I AM

All about problems in Volume 114. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### Re: 11419 - Sam I Am

is not the graph so large?!
Can you describe your graph construction?
Sleep enough after death, it is the time to work.
Mostafa Saad

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

### Re: 11419 - Sam I Am

Number of nodes = number of row + number of column + 2

here I used 1 dummy source and one dummy sink.

898989
Learning poster
Posts: 83
Joined: Wed Feb 01, 2006 12:59 pm
Location: (Fci-cu) Egypt
Contact:

### Re: 11419 - Sam I Am

hmmm

Is not 1000+1000+2 is large?

my idea ( min vertex cover ) is the following graph
Left side (1000 node for ROWs & 1000 node for Cols)
Right Side (each node in the grid)
Draw arcs between lfet to right if left (row/col) covers a node.

This is too much....Can you elaborate in some detaisl how u construct ur graph?
Sleep enough after death, it is the time to work.
Mostafa Saad

emotional blind
A great helper
Posts: 383
Joined: Mon Oct 18, 2004 8:25 am
Location: Bangladesh
Contact:

### Re: 11419 - Sam I Am

My graph is same as yours.

mak(cse_DU)
Learning poster
Posts: 72
Joined: Tue May 30, 2006 5:57 pm
Location: bangladesh

### Re: 11419 - Sam I Am

WooW.
It is a nice minimum vertex cover problem for bipartite graph.
Thanks Jan vaia.
Mak
Help me PLZ!!

shiam
New poster
Posts: 8
Joined: Mon Mar 14, 2011 6:44 am

### Re: 11419 - Sam I Am

emotional blind wrote:My graph is same as yours.
can you please elaborate what have you done ? The min cut is not always indicating the correct nodes.

double_zero
New poster
Posts: 8
Joined: Sat Jun 28, 2014 12:42 pm

### Re: 11419 - SAM I AM

Hello guys, I have some problems with min vertex cover on bipartite graph.

I know that the "max cardinality bipartite matching" equals the number of vertices in "min vertex cover of graph", but how we print those vertices belong to min vertex cover???