New answers tagged graphs
0
votes
Accepted
weighted graph separation algorithm proof
Your algorithm is incorrect. Let $G$ be a cycle on $4$ vertices where edge weights alternate between $2$ and $4$ and consider $k=5$.
The graph obtained from $G$ by keeping all and only the edges with ...
- 23.4k
0
votes
Converting a Directed Acyclic Graph to a Directed Tree
If the undirected version $G'$ of the DAG $G=(V, E)$ is not connected, then there is no polytree that contains all vertices in $V$ and only a subset of the edges in $E$.
If $G'$ is connected, then you ...
- 23.4k
0
votes
Calculate shortest cycle that contains node $s$
In an undirected graph $G$, remove vertex $v$ and find the shortest path between all pairs of vertices in $N(v)$; i.e. Find $d(a,b):=$shortest path between $a,b\in N(v)$ in graph $G'=G-\{v\}$.
Result ...
1
vote
Accepted
Calculate shortest cycle that contains node $s$
To answer the question "why is the linked algorithm correct?", first of all notice that it works for directed graphs.
We want to show that the shortest cycle containing $s$ consists of a ...
- 23.4k
1
vote
Accepted
Efficient algorithm to count number of intersections of n sets
Assuming you really need the number for all pairs of sets and hearing that we are thinking of users in communities you could use the following algorithm which relies on the idea that the the average ...
- 1,106
0
votes
Prove there is an algorithm that needs at most n-1 comparisons to check if n-element array has all equal elements?
Let a sequence of $n$ elements. If all pairs of consecutive elements are equal, then by transitivity all elements are equal. By contradiction, if they are not all equal, then there is certainly a pair ...
- 3,910
1
vote
Accepted
safe edge theorem proof clarification
Although correct, that statement, "$w(T') = w(T) - w(x,y) + w(u,v) \le w(T)$" alone is indeed confusing, since it leaves the impression that $w(T')$ might be smaller than $w(T)$.
Well, the ...
- 34.1k
0
votes
Recursively deleting spanning forest from graph, how many iterations maximum to get to the empty graph?
This was an irrelevant answer that I had to replace manually (since I cannot delete from my current device)
- 10.8k
3
votes
Accepted
Are Control Flow Graphs(CFG) planar?
If this is wrong, can we always write a program whose CFG is planar without loss of function?
Yes, we can.
Suppose we have an arbitrary CFG $G$, which is a finite graph.
It is known that any finite ...
- 188
2
votes
Are Control Flow Graphs(CFG) planar?
First:
If we use your definition of a CFG, they still can be non-planar. Consider the following (silly) piece of code:
...
- 1,106
0
votes
What is the correct complexity of All paths from Source to Target DFS solution?
For directed graph :-
Suppose there are 7 vertices {0,1,2,3,4,5,6} and consider the worst case where every vertex is connected to every other vertex =>
No of edges required to reach from x to y ...
- 1
2
votes
Name and complexity of this problem on bipartite graphs
I don't know a prior result on this particular problem. However, I can show this problem is NP-hard by reducing the hitting set problem.
Suppose we are given an instance of the hitting set problem as ...
- 826
1
vote
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
Induction on the order of G . True for |G| = 1. Assume for |G| = n let prove it for |G| = n +1. Choose a vertex v of minimum degree . Consider H = G - N[v]. Clearly a(G)> = 1 + a(H) > = 1 + sum {...
- 11
1
vote
Alternate proof of the Caro-Wei theorem for lower bounding the independence number
There are several non-probabilisitc proofs :
1/ using greedy algorithm deleting minimum degree :
See : https://www.sciencedirect.com/science/article/pii/S0166218X13001339
https://onlinelibrary.wiley....
- 11
0
votes
Optimality of DSATUR on interval graphs
Yes. DSATUR produces an optimal coloring for interval graphs. My idea is as follows (Please identify any potential issues). We know that a) In DSATUR, once a new vertex has been colored then we should ...
0
votes
Better results for minimum vertex cover algorithms
I proposed a better approximation algorithm for vertex cover problem (a 1.999999-approximation algorithm by solving a well-known SDP model and a randomized procedure). It is not published, yet. But, I ...
2
votes
Accepted
Transitive Closure of a graph
Using Kosaraju's algorithm, you can compute the strongly connected components (SCC) of $G$ in linear time.
The metagraph (or graph of the SCC) is well known to be a DAG. You can then compute the ...
- 7,090
2
votes
Confuse on proof of theorem 22.9 (White-path theorem) Depth-First search (DFS) on Cormen-Leiserson-Rivest-Stein "Introduction to algorithms" book
I'm not sure what the problem is, but I will still try to answer.
The predecessor of $v$ in a path from $u$ to $v$ is the last vertex seen before $v$.
Since there exists a path from $u$ to $v$ then, ...
- 7,090
0
votes
Find a simple path from S to T in a directed graph so that the product of its weights is maximum
$$
\max \prod_{i}p_i\iff \max \sum_{i}\log p_i,\,p_i>0
$$
So it's nearly equal to ask "single source longest path", which is NP-hard in most graphs. There is a Polynomial solution on DAG. ...
- 93
1
vote
Accepted
Find a simple path from S to T in a directed graph so that the product of its weights is maximum
The problem is NP-hard by a reduction from the Hamiltonian-path problem.
If all edge weights are set to some constant $c>1$ and $P$ is a simple path from $s$ to $t$ that maximizes the product of ...
- 23.4k
2
votes
Accepted
Are the clusters in a cluster graph complete graphs?
You are reading it correctly. Those are two different uses of the word "cluster graph".
In graph theory, and usually in computer science, when you refer to a cluster graph it is of the ...
- 13.3k
3
votes
Accepted
Difference between cost and the heuristic function in A* search
Necessary heuristic function is needed for 2nd image, I can't tell why it's so in that image.
But for the common A star algorithm, heuristic is an "Oracle" that guide algorithm to make "...
- 93
0
votes
Question about Complete partially Directed Acyclic Graph
This answer includes some clarification and an answer. The figure in the question is from here. Some clarifications regarding the terms:
Two DAGs are equivalent iff they have the same skeletons and ...
- 101
3
votes
Accepted
Topological sort of minimum costs to finish interdependent tasks
I am assuming here that you are allowed to start tasks in parallel if there is no dependency between them, otherwise I think that no matter what order you do, the total time needed to finish the ...
- 1,403
3
votes
Topological sort of minimum costs to finish interdependent tasks
This problem is basically to find the longest path in a directed acyclic graph (DAG).
Let $cost[t]$ be the number of days it takes to do task $t$.
Let $m[t]$ be the minimum number of days to finish ...
- 34.1k
2
votes
Accepted
FPT algorithm for dominating set
See the FPT algorithm in Linear Time Algorithms for Finding a Dominating Set of Fixed Size in Degenerated Graphs. Since the proof applies for $k$-degenerate graphs, it also applies for graphs whose ...
- 1,024
Top 50 recent answers are included