Re: Vertex Cover implementation
- From: Tor Myklebust <tmyklebu@xxxxxxxxxxxxxxxxxxx>
- Date: Tue, 31 Jul 2007 00:08:02 +0000 (UTC)
GCRhoads <GCRhoads@xxxxxxxxxxxxxxx> wrote:
On Jul 28, 4:09 pm, Francois Delbot <francois.del...@xxxxxxxxx> wrote:
dear all,
i code this simple greedy algorithm for the vertex cover :
let G be a graph
C=empty set
while the number of edges in G is not 0 do
select the vertex u with maximum degree
C=C+{u}
delete u from G
end while
return the vertex cover C
so, my code work perfectly but now i want to improve the speed of my
implementation because i have to do a lot of executions of this
algorithm.
when i select the vertex u with maximum degree, there can be a lot of
vertices of maximum degree and i make a list of them, and then, i
select a vertex at random. this step look very costly.
It shouldn't be that costly. Each vertex can have a field for its
degree. As you are constructing your graph you can update the vertex
degrees. To find the maximum degree vertices requires only a single
pass through your list/array of vertices. When you remove an edge,
you can decrement the degree of the corresponding vertices.
Finding the maximum-degree vertex takes linear time.
did you know how i can improve the speed of this algorithm,
did you know wich structure of graph i have to use to make this
algorithm more speedy ?
You could augment the standard adjacency list representation. With
undirected graphs (vertex cover is defined only for undirected
graphs), each edge appears on two adjacency lists. You could have
these edge records point to each other; you can set these pointers as
you build your initial graph. Now suppose you are deleting the edges
adjacent to some vertex a and the current edge on a's list is a--b. We
can immediately find the corresponding edge on b's list by following
our additional pointer and thus avoid having to traverse b's list to
find it! To be able to delete this edge from the middle of b's list
given only a pointer to it, we have to make the adjacency lists doubly-
linked. This should speed things up.
I would ignore the suggestion to use fibonacci heaps. This is a data
structure that implements a "priority-queue" and I don't see a good
reason to use a priority queue for your algorithm.
Because it's not as slow as your suggestion. Doing a linear scan per
pass will make the algorithm as a whole cost O(|V|^2) time, as opposed
to the O(|E| + |V| log |V|) time bound you get by using a Fibonacci heap
to remember which vertex has highest degree. Any other reasonable data
structure (heaps, tournament trees...) for priority queues will give you
an O(|E| log |V|) algorithm, which is almost the same.
.
- References:
- Vertex Cover implementation
- From: Francois Delbot
- Re: Vertex Cover implementation
- From: GCRhoads
- Vertex Cover implementation
- Prev by Date: The Right Way to Design a Programme
- Next by Date: Re: efficiently finding a subset of data.
- Previous by thread: Re: Vertex Cover implementation
- Next by thread: Book recommendation for Scheme/SML Grad level prep ?
- Index(es):
Relevant Pages
|
