-
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 :
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?
-
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:
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.
-
July 1st, 2014, 01:53 PM
#4
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
-
Forum Rules
|
Click Here to Expand Forum to Full Width
|