Node Cover

This option finds a set of nodes that cover every link.

Input

A space delimited text file.

Format

The first line must be

format cover

Links

Column	Description
1	'l' for link
2	src node name
3	dst node name

Example

format cover
l 0 1
l 0 2
l 1 2
l 1 3
l 2 4
l 3 4
l 3 5

Algorithm

LOOP V over vertices
  IF V is a leaf node ( degree 1 )
     Add V to to cover set
LOOP E over edges
  Set V1, and v2 to the vertices connected by E
  IF V1 and V2 are NOT in set
      Set v to V1
      IF V2 degree > V1 degree
           Set v to V2
      Add v to cover set.

Performance

To find a set of vertices that cover every link of a randomly generated graph of 100,000 vertices and 300,000 edges requires 0.2 seconds