
July 1st, 2014, 09:37 AM
#1
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 :
012345678
Solutions are vertices: 0,2,4,6,8
This problem is known and have any name or is new? Algorithm has other nongraph form?
It is possible not to remove vertices, but add vertices to empty graph while inconsistent?

July 1st, 2014, 10:43 AM
#2
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

July 1st, 2014, 11:40 AM
#3
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:
012: let remove 1
021: let remove 2
102: let remove 0
Full connection: 012 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.

July 1st, 2014, 01:53 PM
#4
Re: Maximal, completely inconsistent graph
Wikipedia: Maximum_independent_set
In general problem is NPhard, 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

Forum Rules

Click Here to Expand Forum to Full Width
OnDemand Webinars (sponsored)
