An algorithm with Minimum vertex cover without considering its performance
- From: wtxwtx@xxxxxxxxx
- Date: 23 Sep 2006 12:06:27 -0700
Hi,
I know that searching for a minimum vertex cover is a NP-Complete in
computing complexity.
I am interested not in its performance, but in an algorithm that can
get a right solution in theory as a mind exercise.
So situation should become much relieved.
1. Please let me know if there are references that had given an
algorithm solution.
2. I will continue my last posting to correct errors happening with the
last posting "Hamburger Principle..."
Given a graph G = (V, E), how to find a minimum vertex cover for the
given graph?
Given graph G = (V, E), vertex cover V' is a subset of V such that
for each edge {u, v} belonging to E at least one of u and v belongs to
V'. Minimum vertex cover V' is the vertex cover whose number of
vertexes is the minimum.
To make discussion simpler, we assume that every vertex has a positive
integer,
starting with 1 to n and input cell have the following structure:
(edge count, edge starting vertex, edge ending vertexs).
For example vertex 1 has edges: (1, 2), (1, 3), (1, 4), then its input
cell
has the following representation: (3, 1, 2, 3, 4). Cell length vary
dependent
on the cell's number of edges.
Here is an algorithm:
1. Count = 0.
2. Sort the input cell serials based on count in increasing order.
3. Count_1 = 0
4. for all vertexes with edge count = 1, do following:
a. Set original starting vertex;
b. Count++;
c. Print out its edge ending vertex #; (only one)
d. Delete its input cell;
e. In the edge ending vertex cell, do the followings:
a. delete the original starting vertex in edge ending
vertexs area;
b. edge count is decreased by 1;
c. if edge count = 1, set current ending vertex as new
original starting vertex
and go to b.
d. if edge count = 0, delete the cell;
5. the remaining graph has all vertexes each with more than 1 edges.
6. How to develop the algorithm is unknown and to be continued.
Why are there 2-4 procedures:
See examples.
1--2--3--4--5
|
6
|
7
When the algorithm reaches procedure 5, it has output:
2, 4, 6 and Count = 3.
8
|
1--2--3--4--5
|
6
|
7
Output: 2, 4, 6 and 8 and Count = 4.
The reason is, no matter what other parts of graph are,
the vertex outputs must include all its branch end terminal.
I have to figure out what the next step should be.
Do you have any smart tips?
My assignment for next one year is to develop a correct algorithm
with minimum vertex cover without considering its performance.
Thank you.
Weng
.
- Follow-Ups:
- Re: An algorithm with Minimum vertex cover without considering its performance
- From: Patricia Shanahan
- Re: An algorithm with Minimum vertex cover without considering its performance
- Prev by Date: Re: (Probably flawed) Polynomial time Graph Isomorphism
- Next by Date: Re: An algorithm with Minimum vertex cover without considering its performance
- Previous by thread: To which field does this belong?
- Next by thread: Re: An algorithm with Minimum vertex cover without considering its performance
- Index(es):
Relevant Pages
|
