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

Post by 898989 » Fri Aug 22, 2008 10:47 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

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

Re: 11419 - Sam I Am

Post by emotional blind » Fri Aug 22, 2008 10:49 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

Post by 898989 » Fri Aug 22, 2008 10:59 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

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

Re: 11419 - Sam I Am

Post by emotional blind » Sat Aug 23, 2008 9:49 pm

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

Post by mak(cse_DU) » Fri Apr 16, 2010 7:16 pm

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

Post by shiam » Wed Aug 07, 2013 10:18 pm

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

Post by double_zero » Fri Feb 06, 2015 10:37 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???

Post Reply

Return to “Volume 114 (11400-11499)”