CodeGuru Home VC++ / MFC / C++ .NET / C# Visual Basic VB Forums Developer.com
Results 1 to 4 of 4
  1. #1
    Join Date
    Jun 2014
    Posts
    21

    Maximal, completely inconsistent graph

    Sorry for my English, if the terminology will be confusing.
    We have graph with vertices: 0..7
    This vertices are connected bidirectional:
    0 with 1
    1 with 2
    3 with 4
    5 with 6
    6 with 7
    7 with 5
    There are 3 consistent components :
    A: 0,1,2
    B: 3,4
    C: 5,6,7
    My problem:
    - I can’t eliminate connections without elimination vertices
    How to eliminate minimal number of vertices to obtain all remaining vertices lonely ?
    In this example I can choose one representative from B and C, but in A I must remove vertice 1
    Another example:
    I have train :
    0-1-2-3-4-5-6-7-8
    Solutions are vertices: 0,2,4,6,8

    This problem is known and have any name or is new? Algorithm has other non-graph form?
    It is possible not to remove vertices, but add vertices to empty graph while inconsistent?

  2. #2
    Join Date
    Jun 2014
    Posts
    21

    Re: Maximal, completely inconsistent graph

    Original problem is:
    I have set of points. I must decimate this points obtain subset points, where distance between each pair is >=dmin.
    I use graphs giving connections between vertices if distance is <dmin

  3. #3
    Join Date
    Jun 2014
    Posts
    21

    Re: Maximal, completely inconsistent graph

    Combinatorial approach:
    I have any idea:
    If we have only one vertex - nothing to do
    If we have connected 0 with 1 - let remove 0 or 1
    If we have three vertices, we have 3 similar cases and one other:
    0-1-2: let remove 1
    0-2-1: let remove 2
    1-0-2: let remove 0
    Full connection: 0-1-2 and 2 with 0 again: let remove two any vertices, if first phase we remove one vertex and have two vertice case.
    Something tells me, that in each phase we must remove vertex with maximal connections. It is true?
    How to do optimal - If I will search maximal vertex in each phase, this is square time. If I first sort them, removing vertex breaks order.

  4. #4
    Join Date
    Jun 2014
    Posts
    21

    Re: Maximal, completely inconsistent graph

    Wikipedia: Maximum_independent_set
    In general problem is NP-hard, but my greedy solution is OK for point set decimation

Tags for this Thread

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  





Click Here to Expand Forum to Full Width

Featured