An algorithm with Minimum vertex cover without considering its performance - Theory

This is a discussion on An algorithm with Minimum vertex cover without considering its performance - Theory ; eKo1 wrote: > eKo1 wrote: > > Perhaps I'm not understanding what a vertex cover is. I thought a > > vertex cover was just the set of all vertices which are incident to > > edges in E. I ...

+ Reply to Thread
Page 2 of 4 FirstFirst 1 2 3 4 LastLast
Results 11 to 20 of 40

An algorithm with Minimum vertex cover without considering its performance

  1. Default Re: An algorithm with Minimum vertex cover without considering its performance

    eKo1 wrote:
    > eKo1 wrote:
    > > Perhaps I'm not understanding what a vertex cover is. I thought a
    > > vertex cover was just the set of all vertices which are incident to
    > > edges in E. I guess I'll have to research what a vertex cover is in
    > > more detail.

    >
    > Let V' be a subset of V. V' is a vertex cover if it satisfies the
    > following test:
    >
    > E' =
    > for each v in V'
    > for each edge e in E
    > if v is incident to e then
    > add e to E'
    > end if
    > end for
    > end for
    > if |E| = |E'| then
    > return true // V' is a vertex cover
    > end if
    > return false
    >
    > Would this be correct?


    Hi eKo1,
    The algorithm you mentioned for a vertex cover is right.

    Here is my full new algorithm that can get minimum vertex cover:

    To make discussion simpler, we assume that every vertex has a positive
    integer, starting with 1 to n and input cells have the following
    structure:
    (edge count, edge starting vertex, edge ending vertexes).

    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 degree, or the number of edges which is
    incident on the cell.

    Here is new full algorithm to get minimum vertex cover:
    1. Count = 0.
    2. If input cell is empty, algorithm ends, otherwise
    Sort the input cell serials based on count in increasing order.
    3. 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
    vertexes 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;
    4. If input cell is empty, algorithm ends, otherwise
    sort the input cell serials based on count in decreasing order.
    5. If there is only one cell that has the largest degree, select the
    cell
    and go to 6. If there are more than one cell that have the equal
    largest degree, select the cell that has not been the end vertex
    of the last selected cell with the largest degree, or select any of
    them
    if all of them have have been the end vertexes of last selected cell

    with the largest degree.
    6. a. Delete its input cell;
    b. clear the last setting of LargestDegreeEndVertexFlag,
    c. for all edge ending vertex cells, do the followings:
    a. delete the original starting vertex in edge ending
    vertexes area;
    b. edge count is decreased by 1;
    c. set new LargestDegreeEndVertexFlag
    and go to 2.

    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.

    Now I give a explanation to the procedure 5-6:
    5-6: when there are no claws, delete the cell with largest degree;
    but at the same time avoid to use the cells that are the end vertexes
    of last select cell with largest degree.

    Example for largest cell selection:
    (5, 1, 2, 3, 4, 5, 6) (vertex 1 has 5 edges)
    (5, 2, 3, 4, 5, 6, 1) (vertex 2 has 5 edges)
    (4, 7, 2, 3, 4, 5, 6) (vertex 7 has 4 edges)

    step 1: It may select vertex 1 or 2; it selects 1:
    (5, 2, 3, 4, 5, 6, 1) --> (4, 2, 3, 4, 5, 6)+
    step 2:
    (4, 2, 3, 4, 5, 6)+
    (4, 7, 2, 3, 4, 5)

    '+' indicates it was an ending vertex of last selection vertex with
    largest degree.

    Both have count = 4, but (4, 2, 3, 4, 5, 6)+ was connected to
    the last selection vertex 1, so it should select (4, 7, 2, 3, 4, 5).

    This method is used to avoid both vertexes on one edge are selected
    to create a situation that would increase chance of duplicate vertex
    selection.

    Manually I tried more than 20 graphs and get the right answers for
    every graph.

    Do you have any smart tips?

    If you can find a graph that fails the algorithm, please let me know.

    Thank you.

    Weng


  2. Default Re: An algorithm with Minimum vertex cover without considering its performance

    eKo1 wrote:
    > eKo1 wrote:
    > > Perhaps I'm not understanding what a vertex cover is. I thought a
    > > vertex cover was just the set of all vertices which are incident to
    > > edges in E. I guess I'll have to research what a vertex cover is in
    > > more detail.

    >
    > Let V' be a subset of V. V' is a vertex cover if it satisfies the
    > following test:
    >
    > E' =
    > for each v in V'
    > for each edge e in E
    > if v is incident to e then
    > add e to E'
    > end if
    > end for
    > end for
    > if |E| = |E'| then
    > return true // V' is a vertex cover
    > end if
    > return false
    >
    > Would this be correct?


    Hi eKo1,
    The algorithm you mentioned for a vertex cover is right.

    Here is my full new algorithm that can get minimum vertex cover:

    To make discussion simpler, we assume that every vertex has a positive
    integer, starting with 1 to n and input cells have the following
    structure:
    (edge count, edge starting vertex, edge ending vertexes).

    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 degree, or the number of edges which is
    incident on the cell.

    Here is new full algorithm to get minimum vertex cover:
    1. Count = 0.
    2. If input cell is empty, algorithm ends, otherwise
    Sort the input cell serials based on count in increasing order.
    3. 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
    vertexes 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;
    4. If input cell is empty, algorithm ends, otherwise
    sort the input cell serials based on count in decreasing order.
    5. If there is only one cell that has the largest degree, select the
    cell
    and go to 6. If there are more than one cell that have the equal
    largest degree, select the cell that has not been the end vertex
    of the last selected cell with the largest degree, or select any of
    them
    if all of them have have been the end vertexes of last selected cell

    with the largest degree.
    6. a. Delete its input cell;
    b. clear the last setting of LargestDegreeEndVertexFlag,
    c. for all edge ending vertex cells, do the followings:
    a. delete the original starting vertex in edge ending
    vertexes area;
    b. edge count is decreased by 1;
    c. set new LargestDegreeEndVertexFlag
    and go to 2.

    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.

    Now I give a explanation to the procedure 5-6:
    5-6: when there are no claws, delete the cell with largest degree;
    but at the same time avoid to use the cells that are the end vertexes
    of last select cell with largest degree.

    Example for largest cell selection:
    (5, 1, 2, 3, 4, 5, 6) (vertex 1 has 5 edges)
    (5, 2, 3, 4, 5, 6, 1) (vertex 2 has 5 edges)
    (4, 7, 2, 3, 4, 5, 6) (vertex 7 has 4 edges)

    step 1: It may select vertex 1 or 2; it selects 1:
    (5, 2, 3, 4, 5, 6, 1) --> (4, 2, 3, 4, 5, 6)+
    step 2:
    (4, 2, 3, 4, 5, 6)+
    (4, 7, 2, 3, 4, 5)

    '+' indicates it was an ending vertex of last selection vertex with
    largest degree.

    Both have count = 4, but (4, 2, 3, 4, 5, 6)+ was connected to
    the last selection vertex 1, so it should select (4, 7, 2, 3, 4, 5).

    This method is used to avoid both vertexes on one edge are selected
    to create a situation that would increase chance of duplicate vertex
    selection.

    Manually I tried more than 20 graphs and get the right answers for
    every graph.

    Do you have any smart tips?

    If you can find a graph that fails the algorithm, please let me know.

    Thank you.

    Weng


  3. Default Re: An algorithm with Minimum vertex cover without considering its performance


    On Sun, 24 Sep 2006, Weng Tianxiang wrote:
    > eKo1 wrote:
    >>
    >> Let V' be a subset of V. V' is a vertex cover if it satisfies the
    >> following test:
    >>
    >> E' =
    >> for each v in V'
    >> for each edge e in E
    >> if v is incident to e then
    >> add e to E'
    >> end if
    >> end for
    >> end for
    >> if |E| = |E'| then
    >> return true // V' is a vertex cover
    >> end if
    >> return false
    >>
    >> Would this be correct?

    >
    > Hi eKo1,
    > The algorithm you mentioned for a vertex cover is right.


    Yes, that's right. (And it suggests a trivial brute-force algorithm
    to find a minimum vertex cover:

    M = V
    for each V' in V
    if (V' is a vertex cover of G) then
    if |V'| < |M| then
    M = V
    end if
    end if
    end for
    return M

    Now M is a minimum vertex cover.)


    > Here is my full new algorithm that can get minimum vertex cover:
    >
    > To make discussion simpler, we assume that every vertex has a positive
    > integer, starting with 1 to n and input cells have the following
    > structure:
    > (edge count, edge starting vertex, edge ending vertexes).
    >
    > 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 degree, or the number of edges which is
    > incident on the cell.


    Whoof, that's a clumsy representation! Next time, consider using a
    more natural representation, such as "Each vertex has a list of
    neighbors. For example, vertex 1 has neighbors {2,3,4}."

    > Here is new full algorithm to get minimum vertex cover:
    > 1. Count = 0.
    > 2. If input cell is empty, algorithm ends, otherwise
    > Sort the input cell serials based on count in increasing order.


    What are the "input cell serials"? I'm guessing you mean to sort the
    cells in increasing order by degree, i.e., the cells with lower degree
    come first in the list. Okay, but let me know if I'm wrong.

    > 3. for all vertexes with edge count = 1, do following:
    > a. Set original starting vertex;


    What?

    > 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
    > vertexes area;


    What?

    > 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;
    > 4. If input cell is empty, algorithm ends, otherwise
    > sort the input cell serials based on count in decreasing order.


    What? What is the "input cell"? What is an "empty" cell --- is ()
    the only empty cell, or could (0, 5) be considered empty too?

    > 5. If there is only one cell that has the largest degree, select the
    > cell
    > and go to 6. If there are more than one cell that have the equal
    > largest degree, select the cell that has not been the end vertex
    > of the last selected cell with the largest degree, or select any of
    > them
    > if all of them have have been the end vertexes of last selected cell


    What? What?

    (snip much more gibberish)

    > Manually I tried more than 20 graphs and get the right answers for
    > every graph.


    Good for you.

    > Do you have any smart tips?


    Yes. Stop trying to find a polynomial algorithm for minimum vertex
    cover until you've read at least one existing (non-polynomial) algorithm
    and understand how it works. Also, try to write in plain English, or,
    failing that, some common programming language.

    > If you can find a graph that fails the algorithm, please let me know.


    Yes, I can. So now you know.

    -Arthur

  4. Default Re: An algorithm with Minimum vertex cover without considering its performance

    Arthur J. O'Dwyer wrote:
    > On Sun, 24 Sep 2006, Weng Tianxiang wrote:
    > > eKo1 wrote:
    > >>
    > >> Let V' be a subset of V. V' is a vertex cover if it satisfies the
    > >> following test:
    > >>
    > >> E' =
    > >> for each v in V'
    > >> for each edge e in E
    > >> if v is incident to e then
    > >> add e to E'
    > >> end if
    > >> end for
    > >> end for
    > >> if |E| = |E'| then
    > >> return true // V' is a vertex cover
    > >> end if
    > >> return false
    > >>
    > >> Would this be correct?

    > >
    > > Hi eKo1,
    > > The algorithm you mentioned for a vertex cover is right.

    >
    > Yes, that's right. (And it suggests a trivial brute-force algorithm
    > to find a minimum vertex cover:
    >
    > M = V
    > for each V' in V
    > if (V' is a vertex cover of G) then
    > if |V'| < |M| then
    > M = V
    > end if
    > end if
    > end for
    > return M
    >
    > Now M is a minimum vertex cover.)
    >
    >
    > > Here is my full new algorithm that can get minimum vertex cover:
    > >
    > > To make discussion simpler, we assume that every vertex has a positive
    > > integer, starting with 1 to n and input cells have the following
    > > structure:
    > > (edge count, edge starting vertex, edge ending vertexes).
    > >
    > > 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 degree, or the number of edges which is
    > > incident on the cell.

    >
    > Whoof, that's a clumsy representation! Next time, consider using a
    > more natural representation, such as "Each vertex has a list of
    > neighbors. For example, vertex 1 has neighbors {2,3,4}."
    >
    > > Here is new full algorithm to get minimum vertex cover:
    > > 1. Count = 0.
    > > 2. If input cell is empty, algorithm ends, otherwise
    > > Sort the input cell serials based on count in increasing order.

    >
    > What are the "input cell serials"? I'm guessing you mean to sort the
    > cells in increasing order by degree, i.e., the cells with lower degree
    > come first in the list. Okay, but let me know if I'm wrong.
    >
    > > 3. for all vertexes with edge count = 1, do following:
    > > a. Set original starting vertex;

    >
    > What?
    >
    > > 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
    > > vertexes area;

    >
    > What?
    >
    > > 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;
    > > 4. If input cell is empty, algorithm ends, otherwise
    > > sort the input cell serials based on count in decreasing order.

    >
    > What? What is the "input cell"? What is an "empty" cell --- is ()
    > the only empty cell, or could (0, 5) be considered empty too?
    >
    > > 5. If there is only one cell that has the largest degree, select the
    > > cell
    > > and go to 6. If there are more than one cell that have the equal
    > > largest degree, select the cell that has not been the end vertex
    > > of the last selected cell with the largest degree, or select any of
    > > them
    > > if all of them have have been the end vertexes of last selected cell

    >
    > What? What?
    >
    > (snip much more gibberish)
    >
    > > Manually I tried more than 20 graphs and get the right answers for
    > > every graph.

    >
    > Good for you.
    >
    > > Do you have any smart tips?

    >
    > Yes. Stop trying to find a polynomial algorithm for minimum vertex
    > cover until you've read at least one existing (non-polynomial) algorithm
    > and understand how it works. Also, try to write in plain English, or,
    > failing that, some common programming language.
    >
    > > If you can find a graph that fails the algorithm, please let me know.

    >
    > Yes, I can. So now you know.
    >
    > -Arthur


    Hi Arthur,
    I cannot read the page. Can you please post the page on the group or
    send me an email?

    My email address is wtxwtx at gmail dot com (without space).

    I don't know if my algorithm is the same as the one you mentioned.

    Actually I checked my algorithm with more than 20 hand-drawn graphs and
    all results generated are the minimum vertex cover, no exception!!!

    Otherwise I couldn't publish my 2nd version so quickly. If another
    error is found, I can also quickly change my design to correct the
    error without destroying the full design.

    The key point is:
    1. First delete all claws until there are no any claws; (Claw is a
    vertex of degree 1).
    2. Next delete the vertex with largest degree and mark its neighbors to
    keep them from being selected next time unless next time all vertexes
    that have the largest degree are its neighbors. Later if a vertex's
    edge is deleted, the vertex's neighbor mark should be deleted too if
    any.
    3. Repeat 1. and 2. until all input cells are deleted.

    I will start writing a program in C and write some programs to generate
    random graphs to check if there are any violations:
    1. Randomly generate a graph;
    2. Generate its minimum vertex cover, m= |V'| by my program.
    3. Check C(n, m-1) choices to see if any of them meets the minimum
    vertex cover.

    I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
    It has a problem 35.1-3:
    Professor Nixon proposes the following heuristic to solve the
    vertex-cover problem. Repeatedly select a vertex of highest degree, and
    remove all of its incident edges. Give an example to show that the
    professor's heuristic doesn't not have an approximation ratio of 2.
    (Hint: Try a bipartite graph with vertexes of uniform degree on the
    left and vertexes of varying degree on the right. )

    That is exactly what I suggested in my first version. But with the
    problem exposed, I changed my strategy to delete any claws first, then
    do the selection.

    If you can post a graph that fails my algorithm, it will be great!!!

    Thank you.

    Weng


  5. Default Re: An algorithm with Minimum vertex cover without considering itsperformance

    Weng Tianxiang wrote:
    ....
    > The key point is:
    > 1. First delete all claws until there are no any claws; (Claw is a
    > vertex of degree 1).
    > 2. Next delete the vertex with largest degree and mark its neighbors to
    > keep them from being selected next time unless next time all vertexes
    > that have the largest degree are its neighbors. Later if a vertex's
    > edge is deleted, the vertex's neighbor mark should be deleted too if
    > any.
    > 3. Repeat 1. and 2. until all input cells are deleted.


    At some stages in all this deleting, you presumably tag some vertices as
    being members of the resulting cover. Could you restate the algorithm
    making it clear which they are?

    Thanks,

    Patricia

  6. Default Re: An algorithm with Minimum vertex cover without considering its performance


    Patricia Shanahan wrote:
    > Weng Tianxiang wrote:
    > ...
    > > The key point is:
    > > 1. First delete all claws until there are no any claws; (Claw is a
    > > vertex of degree 1).
    > > 2. Next delete the vertex with largest degree and mark its neighbors to
    > > keep them from being selected next time unless next time all vertexes
    > > that have the largest degree are its neighbors. Later if a vertex's
    > > edge is deleted, the vertex's neighbor mark should be deleted too if
    > > any.
    > > 3. Repeat 1. and 2. until all input cells are deleted.

    >
    > At some stages in all this deleting, you presumably tag some vertices as
    > being members of the resulting cover. Could you restate the algorithm
    > making it clear which they are?
    >
    > Thanks,
    >
    > Patricia


    Hi Patricia,
    Yes.

    1. First delete all claws until there are no any claws; (Claw is a
    vertex of degree 1).
    output claws's only neighbor vertexes as members of the minimum vertex
    cover;

    1--2--3--4--5--6--7
    |
    8
    |
    9
    Vertex 1 is a claw and deleted, output vertex 2 because it is vertex
    1's neighbor, and vertex 2 is deleted. When one edge of vertex 2 is
    deleted, vertex 3 become a claw and is deleted, then output vertex 4,
    vertex 3's neighbor; vertex 8 become a claw and is deleted, output
    vertex 9; vertex 5 is a claw, output vertex 6.
    So the minimum vertex cover is:
    2, 4, 6, 9. |V'| = 4.

    2. Next delete the vertex with the largest degree, output the vertex as
    a member of the minimum vertex cover and mark its neighbors to keep
    them from being selected next time unless next time all vertexes that
    have the largest degree are its neighbors. Later if a vertex's edge is
    deleted, the vertex's neighbor mark should be deleted too if any.

    (5, 1, 2, 3, 4, 5, 6)
    (5, 2, 1, 3, 5, 6, 7)
    (5, 3, 1, 2, 4, 5, 6)

    Select any one of above 3 vertexes, delete it, it become (when the
    first is selected):
    (4, 2, 3, 5, 6, 7)+
    (4, 3, 2, 4, 5, 6)+

    '+' means it is a neighbor of the deleted vertex with the largest
    degree. On next selectiono, If one of vertexes of the largest degree
    has a neighbor mark, it must not selected unless all vertexes of the
    largest degree are the neighbors of deleted vertexes of the largest
    degree.

    Now any of the two above vertexes can be deleted and output because
    both are the neighbors.

    3. Repeat 1. and 2. until all input cells are deleted.

    If you can list a graph that fails my algorithm, you beat me.

    Thank you.

    Weng


  7. Default Re: An algorithm with Minimum vertex cover without considering itsperformance

    Weng Tianxiang wrote:
    ....
    > If you can list a graph that fails my algorithm, you beat me.


    I wish my algorithm design professor had taken that attitude. It would
    have made homeworks much easier. Instead, he insisted on proofs that my
    algorithms gave correct answers, as well as meeting their claimed time
    complexity.

    Patricia

  8. Default Re: An algorithm with Minimum vertex cover without considering its performance


    David Ashley wrote:
    > Weng Tianxiang wrote:
    > > Arthur J. O'Dwyer wrote:
    > >
    > >>On Sun, 24 Sep 2006, Weng Tianxiang wrote:
    > >>
    > >>>eKo1 wrote:
    > >>>
    > >>>>Let V' be a subset of V. V' is a vertex cover if it satisfies the
    > >>>>following test:
    > >>>>
    > >>>>E' =
    > >>>>for each v in V'
    > >>>> for each edge e in E
    > >>>> if v is incident to e then
    > >>>> add e to E'
    > >>>> end if
    > >>>> end for
    > >>>>end for
    > >>>>if |E| = |E'| then
    > >>>> return true // V' is a vertex cover
    > >>>>end if
    > >>>>return false
    > >>>>
    > >>>>Would this be correct?
    > >>>
    > >>>Hi eKo1,
    > >>>The algorithm you mentioned for a vertex cover is right.
    > >>
    > >> Yes, that's right. (And it suggests a trivial brute-force algorithm
    > >>to find a minimum vertex cover:
    > >>
    > >> M = V
    > >> for each V' in V
    > >> if (V' is a vertex cover of G) then
    > >> if |V'| < |M| then
    > >> M = V
    > >> end if
    > >> end if
    > >> end for
    > >> return M
    > >>
    > >>Now M is a minimum vertex cover.)
    > >>
    > >>
    > >>
    > >>>Here is my full new algorithm that can get minimum vertex cover:
    > >>>
    > >>>To make discussion simpler, we assume that every vertex has a positive
    > >>>integer, starting with 1 to n and input cells have the following
    > >>>structure:
    > >>>(edge count, edge starting vertex, edge ending vertexes).
    > >>>
    > >>>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 degree, or the number of edges which is
    > >>>incident on the cell.
    > >>
    > >> Whoof, that's a clumsy representation! Next time, consider using a
    > >>more natural representation, such as "Each vertex has a list of
    > >>neighbors. For example, vertex 1 has neighbors {2,3,4}."
    > >>
    > >>
    > >>>Here is new full algorithm to get minimum vertex cover:
    > >>>1. Count = 0.
    > >>>2. If input cell is empty, algorithm ends, otherwise
    > >>> Sort the input cell serials based on count in increasing order.
    > >>
    > >> What are the "input cell serials"? I'm guessing you mean to sort the
    > >>cells in increasing order by degree, i.e., the cells with lower degree
    > >>come first in the list. Okay, but let me know if I'm wrong.
    > >>
    > >>
    > >>>3. for all vertexes with edge count = 1, do following:
    > >>> a. Set original starting vertex;
    > >>
    > >> What?
    > >>
    > >>
    > >>> 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
    > >>> vertexes area;
    > >>
    > >> What?
    > >>
    > >>
    > >>> 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;
    > >>>4. If input cell is empty, algorithm ends, otherwise
    > >>> sort the input cell serials based on count in decreasing order.
    > >>
    > >> What? What is the "input cell"? What is an "empty" cell --- is ()
    > >>the only empty cell, or could (0, 5) be considered empty too?
    > >>
    > >>
    > >>>5. If there is only one cell that has the largest degree, select the
    > >>>cell
    > >>> and go to 6. If there are more than one cell that have the equal
    > >>> largest degree, select the cell that has not been the end vertex
    > >>> of the last selected cell with the largest degree, or select any of
    > >>>them
    > >>> if all of them have have been the end vertexes of last selected cell
    > >>
    > >> What? What?
    > >>
    > >>(snip much more gibberish)
    > >>
    > >>
    > >>>Manually I tried more than 20 graphs and get the right answers for
    > >>>every graph.
    > >>
    > >> Good for you.
    > >>
    > >>
    > >>>Do you have any smart tips?
    > >>
    > >> Yes. Stop trying to find a polynomial algorithm for minimum vertex
    > >>cover until you've read at least one existing (non-polynomial) algorithm
    > >>and understand how it works. Also, try to write in plain English, or,
    > >>failing that, some common programming language.
    > >>
    > >>
    > >>>If you can find a graph that fails the algorithm, please let me know.
    > >>
    > >> Yes, I can. So now you know.
    > >>
    > >>-Arthur

    > >
    > >
    > > Hi Arthur,
    > > I cannot read the page. Can you please post the page on the group or
    > > send me an email?
    > >
    > > My email address is wtxwtx at gmail dot com (without space).
    > >
    > > I don't know if my algorithm is the same as the one you mentioned.
    > >
    > > Actually I checked my algorithm with more than 20 hand-drawn graphs and
    > > all results generated are the minimum vertex cover, no exception!!!
    > >
    > > Otherwise I couldn't publish my 2nd version so quickly. If another
    > > error is found, I can also quickly change my design to correct the
    > > error without destroying the full design.
    > >
    > > The key point is:
    > > 1. First delete all claws until there are no any claws; (Claw is a
    > > vertex of degree 1).
    > > 2. Next delete the vertex with largest degree and mark its neighbors to
    > > keep them from being selected next time unless next time all vertexes
    > > that have the largest degree are its neighbors. Later if a vertex's
    > > edge is deleted, the vertex's neighbor mark should be deleted too if
    > > any.
    > > 3. Repeat 1. and 2. until all input cells are deleted.
    > >
    > > I will start writing a program in C and write some programs to generate
    > > random graphs to check if there are any violations:
    > > 1. Randomly generate a graph;
    > > 2. Generate its minimum vertex cover, m= |V'| by my program.
    > > 3. Check C(n, m-1) choices to see if any of them meets the minimum
    > > vertex cover.
    > >
    > > I have "An introduction to Algorithm" written by Thomas H. Cormen etc.
    > > It has a problem 35.1-3:
    > > Professor Nixon proposes the following heuristic to solve the
    > > vertex-cover problem. Repeatedly select a vertex of highest degree, and
    > > remove all of its incident edges. Give an example to show that the
    > > professor's heuristic doesn't not have an approximation ratio of 2.
    > > (Hint: Try a bipartite graph with vertexes of uniform degree on the
    > > left and vertexes of varying degree on the right. )
    > >
    > > That is exactly what I suggested in my first version. But with the
    > > problem exposed, I changed my strategy to delete any claws first, then
    > > do the selection.
    > >
    > > If you can post a graph that fails my algorithm, it will be great!!!
    > >
    > > Thank you.
    > >
    > > Weng
    > >

    >
    > Weng,
    >
    > Did you mean to post this to comp.arch.fpga?
    >
    > It's an interesting problem and all, but...?
    >
    > -Dave
    >
    > --
    > David Ashley http://www.xdr.com/dash
    > Embedded linux, device drivers, system architecture


    Hi David,
    Yes, I post it for comp.arch.fpga too.

    1. comp.arch.fpga has a group of engineers who have many experiences
    with logic design, are talent and should pay attention to the deepest
    problem in computing complexity.

    2. I dream someday we can design a NP machine that runs all NP problems
    in polynomial time using a FPGA chip. Personally I think Turing machine
    should be dying with powerful FPGA chips growing and the fact should be
    reflected in computing theory.

    3. The above posting is my a small step in a direction I am thinking is
    right: first to design an algorithm that is not using brute force, but
    some smart ideas of the special problem.

    4. I select the minimum vertex cover because its memory will never be
    expanded and it depends on a smarter selection to finish the cover.

    5. At the current moment, I am devoting to design an algorithm that
    works with minimum vertex cover.

    6. If the algorithm works, all of us have a chance to finish a NP
    machine with performance in polynomial time.

    Thank you.

    jWeng


  9. Default Re: An algorithm with Minimum vertex cover without considering its performance


    Patricia Shanahan wrote:
    > Weng Tianxiang wrote:
    > ...
    > > If you can list a graph that fails my algorithm, you beat me.

    >
    > I wish my algorithm design professor had taken that attitude. It would
    > have made homeworks much easier. Instead, he insisted on proofs that my
    > algorithms gave correct answers, as well as meeting their claimed time
    > complexity.
    >
    > Patricia


    Hi Patricia,
    1. Yes, I have to prove the following theorem:
    If a graph has no claws (vertex of degree 1), the vertex with the
    largest degree can be a member of the minimum vertex cover.

    2. I am doing the following things:
    a. Develop the algorithm in C;
    b. Develop an algorithm in C that can generate random graphs;
    c. Feed the graphs to my algorithm and generate |V'| data;
    d. Enumerate all cover options of C(N, |V'|-1) to confirm that there is
    no graph cover with less degrees.

    It takes time, but if all people help me, it will be great!

    Thank you.

    Weng


  10. Default Re: An algorithm with Minimum vertex cover without considering itsperformance

    [comp.arch.fpga deleted from newsgroups. I don't think my comments are
    on-topic there].

    Weng Tianxiang wrote:
    .....
    > 1. First delete all claws until there are no any claws; (Claw is a
    > vertex of degree 1).
    > output claws's only neighbor vertexes as members of the minimum vertex
    > cover;
    >
    > 1--2--3--4--5--6--7
    > |
    > 8
    > |
    > 9
    > Vertex 1 is a claw and deleted, output vertex 2 because it is vertex
    > 1's neighbor, and vertex 2 is deleted. When one edge of vertex 2 is
    > deleted, vertex 3 become a claw and is deleted, then output vertex 4,
    > vertex 3's neighbor; vertex 8 become a claw and is deleted, output
    > vertex 9; vertex 5 is a claw, output vertex 6.
    > So the minimum vertex cover is:
    > 2, 4, 6, 9. |V'| = 4.
    >
    > 2. Next delete the vertex with the largest degree, output the vertex as
    > a member of the minimum vertex cover and mark its neighbors to keep
    > them from being selected next time unless next time all vertexes that
    > have the largest degree are its neighbors. Later if a vertex's edge is
    > deleted, the vertex's neighbor mark should be deleted too if any.
    >
    > (5, 1, 2, 3, 4, 5, 6)
    > (5, 2, 1, 3, 5, 6, 7)
    > (5, 3, 1, 2, 4, 5, 6)
    >
    > Select any one of above 3 vertexes, delete it, it become (when the
    > first is selected):
    > (4, 2, 3, 5, 6, 7)+
    > (4, 3, 2, 4, 5, 6)+
    >
    > '+' means it is a neighbor of the deleted vertex with the largest
    > degree. On next selectiono, If one of vertexes of the largest degree
    > has a neighbor mark, it must not selected unless all vertexes of the
    > largest degree are the neighbors of deleted vertexes of the largest
    > degree.
    >
    > Now any of the two above vertexes can be deleted and output because
    > both are the neighbors.
    >
    > 3. Repeat 1. and 2. until all input cells are deleted.
    >
    > If you can list a graph that fails my algorithm, you beat me.


    1-2-3
    | | |
    4-5-6
    | | |
    7-8-9

    There is a four element vertex cover, {2,4,6,8}.

    There is no degree one vertex, so the first pick will be 5, the highest
    degree vertex in the graph. Once 5 has been picked, you are left with a
    loop of eight vertices, and must pick four of them to complete the
    cover. The even number vertices are neighbors of 5, so the next pick
    will be one of the remaining odd number vertices. After that, step 1
    picks odd number vertices, resulting in the five element cover {1,3,5,7,9}.

    Even if you tweak your algorithm to deal with this case, remember that
    to claim to have a minimum vertex cover you really should be thinking in
    terms of proving, for every graph, that your algorithm produces a vertex
    cover and no vertex cover can contain fewer vertices.

    Patricia

+ Reply to Thread
Page 2 of 4 FirstFirst 1 2 3 4 LastLast

Similar Threads

  1. Reduction from Vertex Cover to SAT
    By Application Development in forum Theory
    Replies: 0
    Last Post: 10-29-2007, 10:04 AM
  2. vertex cover kernelization
    By Application Development in forum Theory
    Replies: 0
    Last Post: 08-29-2007, 02:02 AM
  3. Vertex Cover implementation
    By Application Development in forum Theory
    Replies: 6
    Last Post: 08-04-2007, 01:28 AM
  4. Minimum Vertex Cover of a Tree
    By Application Development in forum Theory
    Replies: 13
    Last Post: 11-02-2006, 12:50 AM
  5. Re: Minimum Spanning Tree Algorithm Question
    By Application Development in forum Theory
    Replies: 0
    Last Post: 05-02-2006, 07:22 PM