Stack Overflow
Stack Overflow

Questions tagged [independent-set]

32 questions
15
votes
3 answers

algorithm to find max independent set in a tree

I need an algorithm to find max independent set in a tree. I'm thinking start from all leaf nodes, and then delete the direct parent nodes to these leaf nodes, then choose the parent nodes of the parent nodes we deleted, repeat this procedure…
starcaller
  • 979
  • 3
  • 16
  • 25
11
votes
1 answer

How to create mask in a machine independent way?

So I'm practicing some programming interview questions, and stumbled across this sample pdf which recommends "Understand how to use masks and create them in an machine independent way". But it doesn't eloborate the difference between machine…
danglingPointer
  • 882
  • 8
  • 32
7
votes
2 answers

Maximum Independent Set Algorithm

I don't believe there exists an algorithm for finding the maximum independent vertex set in a bipartite graph other than the brute force method of finding the maximum among all possible independent sets. I am wondering about the pseudocode to find…
user1084113
  • 932
  • 3
  • 15
  • 31
6
votes
3 answers

How to find independent points in a unit square in O(n log n)?

Consider a unit square containing n 2D points. We say that two points p and q are independent in a square, if the Euclidean distance between them is greater than 1. A unit square can contain at most 3 mutually independent points. I would like to…
user2311963
  • 143
  • 6
6
votes
2 answers

Maximum weighted independent set in bipartite graph

Given bipartite graph. Each vertex has some integer value - weight. Is it possible to find maximum weighted independent vertex set in this graph in polynomial time? If such solution exists, what is the algorithm for this problem?
juver
  • 236
  • 2
  • 8
4
votes
1 answer

How can 3-SAT be reduced to Independent set?

I was reading about NP hardness from here (pages 8, 9) and in the notes the author reduces a problem in 3-SAT form to a graph that can be used to solve the maximum independent set problem. In the example, the author converts the following 3-SAT…
Arat254
  • 449
  • 2
  • 5
  • 17
3
votes
2 answers

Independent set in a graph

As you know finding maximum independent set is NP. Is there an algorithm to find out whether a given graph has an Independent set of at least k vertices? Note that we don't want to find it. We just want to find out if such thing exists.
user182513
3
votes
1 answer

How to find maximum independent set of a directed acyclic graph?

Say we have a graph that is similar to a linked list (or a directed acyclic graph). An independent set consists of nodes that don't share edges with any other node in the set. If each node is weighted, how can we calculate the max possible value of…
Sticky
  • 3,671
  • 5
  • 34
  • 58
2
votes
3 answers

Filter a list of images by similarity relationship

I have a list of images names and a (thresholded) similarity matrix for them. The similarity relationship is reflexive and symmetric but not necessary transitive, i.e. if image_i is similar to image_j and to image_k, then it doesn't necessary mean…
Andreas K.
  • 9,282
  • 3
  • 40
  • 45
2
votes
0 answers

extremal index in r extremes package

I want to confirm that the data is iid. I am investigating hourly precipitation data. The attached data is q99 of 7 gauges within a region and they should be iid by definition (I am taking a maximum number of one value/day). I am using the…
Moe_D
  • 73
  • 6
1
vote
1 answer

Time complexity of greedy algorithm to find a maximal independent set of a graph

A simple greedy algorithm to find a maximal independent set, I think it will take O(n) time since no vertex will be visited more than twice. Why wiki said it would take O(m) time? Greedy(G) while G is not empty (visited V in an arbitrary order) …
高翔宇
  • 11
  • 1
1
vote
0 answers

Reduce SAT <=p Independent Set

I am a bit confused. I know how to reduce 3-SAT to IS. An example of transforming 3-SAT to IS graph would be create a graph representing each clause of the 3-SAT and then joining the x and !x and then submitting it to IS. How would we apply this to…
lazycamper
  • 107
  • 1
  • 8
1
vote
0 answers

Gauss-based Linear Independence Test for Binary vectors

I programmed a version of Gaussian Elimination to verify linear independence of a set of Binary vectors. It inputs a matrix (mxn) to evaluate and return: True (Linear Independent): No zero row was found. False (Linear Dependent): If the last row…
mitxael
  • 52
  • 7
1
vote
1 answer

Algorithm: How to find the number of independent sets in a tree?

I'm thinking that there are two cases for each sub-tree: the root is in the independent set and the root is not in the set. How to write a recursive algorithm for finding the number of independent sets in a tree? The tree is…
jas7
  • 2,893
  • 6
  • 23
  • 36
1
vote
1 answer

Finding minimum indepedent dominating set using a greedy algorithm

I developed an algorithm that finds the minimum independent dominating set of a graph based on a distance constraint. (I used Python and NetworkX to generate graphs and get the pairs) The algorithm uses a brute force approach: Find all possible…
knewit
  • 55
  • 1
  • 6
1
2 3