Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,666
questions
11
votes
2
answers
3k
views
Chromatic polynomial of a square
Consider a square, ABCD. Intuitively it seemed to me that its chromatic polynomial is $\lambda(\lambda - 1)(\lambda - 1)(\lambda - 2)$ where there are $\lambda$ colours available..
That is there are $...
- 529
5
votes
1
answer
2k
views
Simple Task-Assignment Problem
I have this simple 'assignment' problem:
We have a set of agents $A = \{a_1, a_2, \dotso, a_n\}$ and set of tasks $T= \{t_1, t_2, \dotso, t_m\}$. Note that $m$ is not necessarily equal to $n$. Unlike ...
- 270
9
votes
2
answers
1k
views
Size of Maximum Matching in Bipartite Graph
Am I correct in my observation that the cardinality of the maximum matching $M$ of a bipartite graph $G(U, V, E)$ is always equal to $\min(|U|, |V|)$?
- 270
12
votes
2
answers
2k
views
Minimal Spanning Tree With Double Weight Parameters
Consider a graph $G(V,E)$. Each edge $e$ has two weights $A_e$ and $B_e$. Find a spanning tree that minimizes the product $\left(\sum_{e \in T}{A_e}\right)\left(\sum_{e \in T}{B_e}\right)$. The ...
- 1,485
5
votes
1
answer
8k
views
Finding the Shortest path in undirected weighted graph
Is there an algorithm for finding the shortest path in an undirected weighted graph?
- 59
28
votes
2
answers
602
views
How to efficiently determine whether a given ladder is valid?
At my local squash club, there is a ladder which works as follows.
At the beginning of the season we construct a table with the name of each
member of the club on a separate line.
We then write the ...
- 399
4
votes
1
answer
712
views
Why do the swap step in Prim's algorithm for minimum spanning trees?
I was watching the video lecture from MIT on Prim's algorithm for minimum spanning trees.
Why do we need to do the swap step for proving the theorem that if we choose a set of vertices in minimum ...
- 1,181
3
votes
1
answer
1k
views
What is the probability of friendship conditioned on the number of mutual friends
Let Alice and Bob be two users chosen uniformly at random from a social network (e.g. Facebook). What is the probability that they are friends assuming that they share $k$ mutual friends?
I am ...
- 21.9k
4
votes
2
answers
3k
views
Finding odd directed circuit
I want to write an algorithm to find whether a directed circuit whose length is odd exists in a strongly connected digraph.
Can anyone help me how to proceed with this problem???
- 49
6
votes
0
answers
774
views
Minimum vertex-weight directed spanning tree where the weight function depends on the tree
Given a directed graph $G=(V,E)$ and a node $r\in V$, I need to grow a tree $T$ rooted at $r$ that has a minimum weight and spans all reachable nodes in $G$.
The weight function assigns a non-...
- 61
6
votes
0
answers
1k
views
A variation in Ford-Fulkerson algorithm
Suppose that we redefine the residual network to disallow edges into $s$. Argue that the procedure FORD-FULKERSON still correctly computes a maximum flow.
I was thinking that when we augment a path ...
- 377
26
votes
4
answers
16k
views
Finding the minimum cut of an undirected graph
Here's a question from a past exam I'm trying to solve:
For an undirected graph $G$ with positive weights $w(e) \geq 0$, I'm trying to find the minimum cut. I don't know other ways of doing that ...
- 1,697
4
votes
0
answers
2k
views
Show that the Minimum spanning tree Reduce Algorithm runs in O(E) on sparse graphs
This is a problem from CLRS 23-2 that I'm trying to solve. The problem assumes that given graph G is very sparse connected. It wants to improve further over Prim's algorithm $O(E + V \lg V)$. The idea ...
- 309
3
votes
1
answer
207
views
Find the lightest weight of a path between $u$ to $v$ that contains no more then $k$ edges (If there's one)
Given a directed and strongly connected graph $G=(V,E)$, weight function $w: E \to \mathbb{R}$ and two distinct vertices $u,v \in V$. We know that there aren't negative cycles.
I need to find ...
- 1,697
4
votes
1
answer
118
views
For a graph $G$ find the minimal $t$ such $G(t)=(V,E(t))$ is connected
Given a connected and directed graph $G=(V,E)$ with positive weights on the edges. for every $t>0$ we define $E(t)$ to be the group of edges with weight lower or equal than $t$. I need to find an ...
- 1,697
2
votes
1
answer
87
views
Given a mechanical assembly as a graph, how to find an upper bound on number of assembly paths
The rules are that you can only build from an existing part, so in the example below, B is the only option for the first move = A.
A mechanical assembly might be represented as follows:
...
- 213
11
votes
1
answer
5k
views
Graphs that cause DFS and BFS to process nodes in the exact same order
For some graphs, DFS and BFS search algorithms process nodes in the exact same order provided that they both start at the same node. Two examples are graphs that are paths and graphs that are star-...
- 3,650
39
votes
4
answers
53k
views
Algorithm that finds the number of simple paths from $s$ to $t$ in $G$
Can anyone suggest me a linear time algorithm that takes as input a directed acyclic graph $G=(V,E)$ and two vertices $s$ and $t$ and returns the number of simple paths from $s$ to $t$ in $G$.
I have ...
- 899
7
votes
0
answers
360
views
Worst-case sparse graphs for Hopcroft-Karp Algorithm
Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and ...
- 699
2
votes
1
answer
777
views
Why does Prim's algorithm keep track of a node's parent?
There is an obvious similarity in workings between Prim's algorithm and Dijkstra's algorithm, however I see no reason for Prim's algorithm to keep track of a node's parent. In Dijkstra's algorithm, ...
user1422
19
votes
5
answers
18k
views
Maximum Independent Set of a Bipartite Graph
I'm trying to find the Maximum Independent Set of a Biparite Graph.
I found the following in some notes "May 13, 1998 - University of Washington - CSE 521 - Applications of network flow":
Problem:
...
- 699
6
votes
1
answer
3k
views
Maximum Independent Subset of 2D Grid Subgraph
In the general case finding a Maximum Independent Subset of a Graph is NP-Hard.
However consider the following subset of graphs:
Create an $N \times N$ grid of unit square cells.
Build a graph $G$ ...
- 699
21
votes
1
answer
1k
views
Generating inputs for random-testing graph algorithms?
When testing algorithms, a common approach is random testing: generate a significant number of inputs according to some distribution (usually uniform), run the algorithm on them and verify correctness....
- 71.6k
25
votes
4
answers
48k
views
Am I right about the differences between Floyd-Warshall, Dijkstra and Bellman-Ford algorithms?
I've been studying the three and I'm stating my inferences from them below. Could someone tell me if I have understood them accurately enough or not? Thank you.
Dijkstra algorithm is used only when ...
Programming Noob
5
votes
1
answer
4k
views
Determining Probability from a Graph
Lets say I have node A that connects to 10 other nodes. 6 of those nodes have Property 1 and the other 4 have Property 2. How can I easily determining the probability of landing on a node with ...
- 293
9
votes
5
answers
2k
views
Standard or Top Text on Applied Graph Theory
I am looking for a reference text on applied graph theory and graph algorithms. Is there a standard text used in most computer science programs? If not, what are the most respected texts in the ...
- 163
7
votes
1
answer
1k
views
Greedy choice and matroids (greedoids)
As I was going through the material about the greedy approach, I came to know that a knowledge on matroids (greedoids) will help me approaching the problem properly. After reading about matroids I ...
- 167
8
votes
4
answers
4k
views
Is it intuitive to see that finding a Hamiltonian path is not in P while finding Euler path is?
I am not sure I see it. From what I understand, edges and vertices are complements for each other and it is quite surprising that this difference exists.
Is there a good / quick / easy way to see ...
- 1,067
8
votes
2
answers
2k
views
An edge that connects more than two nodes in a graph?
Is there a way to create a single edge on a graph that connects 3 or more nodes? For example, let's say that the probability of Y occurring after X is 0.1, and the probability of Z occurring after Y ...
- 293
4
votes
1
answer
623
views
From in-order representation to binary tree
Is there a way to reconstruct a binary tree just from its in-order representation?
I've searched the internet, but I could only find solutions for reconstructing a binary tree from inorder and ...
papen
2
votes
1
answer
644
views
Reason for global update steps in the push-relabel algorithm
I know why and how the push relabel algorithm works for solving the max-flow problem. But why is a global update step required?
- 139
10
votes
2
answers
4k
views
What is the average height of a binary tree?
Is there any formal definition about the average height of a binary tree?
I have a tutorial question about finding the average height of a binary tree using the following two methods:
The natural ...
- 775
5
votes
3
answers
2k
views
Assign m agents to N points by minimizing the total distance
Suppose we have $N$ fixed points (set $S$ with $|S|=N$) on the plane and $m$ agents with fixed, known initial positions ($m<N$) outside $S$. We should transfer the agents so that in our final ...
- 51
4
votes
1
answer
188
views
Is finding dead-end nodes in NL?
Given a directed graph $G$ and two nodes $s,t$, decide whether there is some node $s'$ such that $s'$ is reachable from $s$ while $t$ is not reachable from $s'$.
I am wondering whether this problem ...
- 113
4
votes
1
answer
398
views
Vertex coloring with an upper bound on the degree of the nodes
Consider the set of graphs in which the maximum degree of the vertices is a constant number $\Delta$ independent of the number of vertices. Is the vertex coloring problem (that is, color the vertices ...
- 541
1
vote
2
answers
737
views
Existence of a route following one-way streets
I am trying to understand the approach for this problem:
"If all streets are one way, there is still a legal way to drive from
one intersection to another"
The question is to prove that it can ...
- 111
4
votes
1
answer
8k
views
Is finding the longest path of a graph NP-complete?
The problem of finding the largest subgraph of a graph that has a Hamiltonian path can be restated as finding the longest path of a graph. Is this NP-complete? Also, is finding the $k$-length path of ...
- 249
5
votes
1
answer
408
views
Is it possible to always construct a hamiltonian path on a tournament graph by sorting?
Is it possible to always construct a hamiltonian path on a tournament graph $G=(V,E)$ by sorting (using any sorting algorithm) with the following total order:
$\qquad \displaystyle a \leq b \iff (a,b)...
- 153
5
votes
1
answer
733
views
NP-completeness of graph isomorphism through edge contractions with an edge validity condition
Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset ...
- 61
3
votes
1
answer
248
views
What is the significance of the semi clustering formula in the Google Pregel paper?
Semi clustering algorithm is mentioned in the Google Pregel paper. The score of a semi cluster is calculated using the below formula
$\qquad \displaystyle S_c =\frac{I_c - f_BB_c}{\frac{1}{2}V_c(V_c -...
- 131
16
votes
2
answers
26k
views
Prove that every two longest paths have at least one vertex in common
If a graph $G$ is connected and has no path with a length greater than $k$, prove that every two paths in $G$ of length $k$ have at least one vertex in common.
I think that that common vertex ...
- 899
3
votes
1
answer
664
views
How to random-generate a graph with Pareto-Lognormal degree nodes?
I have read that the degree of nodes in a "knowledge" graph of people roughly follows a power law distribution, and more exactly can be approximated with a Pareto-Lognormal distribution.
Where can I ...
- 133
7
votes
2
answers
541
views
Balanced weighting of edges in cactus graph
Given a cactus, we want to weight its edges in such a way that
For each vertex, the sum of the weights of edges incident to the vertex is no more than 1.
The sum of all edge weights is maximized.
...
- 227
1
vote
1
answer
3k
views
3-dimensional matching approximation algorithm (implementation details)
I have a run-time implementation question regarding the 3-dimensional (unweighted 2-)approximation algorithm below:
How can I construct the maximum matching M_r in S_r in linear time in line 8?
$X, Y,...
- 13
4
votes
0
answers
191
views
Proof of NP-completeness of graph isomorphism through edge contractions that reduce a metric [duplicate]
Duplicate:
NP-completeness of graph isomorphism through edge contractions with an edge validity condition
I know that graph contractability is $NP$-complete. To be specific given $G=(V_1,E_1)$ ...
Yinfang Zhuang
8
votes
1
answer
335
views
Algorithm to test a graph for $t$-transitivity
I am looking for an algorithm, which given a graph $G$ and a natural number $t$, determines if $G$ is $t$-transitive.
I am also interested in knowing if this problem is in P, NP, NPC or some other ...
- 651
17
votes
1
answer
6k
views
Getting parallel items in dependency resolution
I have implemented a topological sort based on the Wikipedia article which I'm using for dependency resolution, but it returns a linear list. What kind of algorithm can I use to find the independent ...
- 273
7
votes
2
answers
430
views
Is there a formal name for this graph operation?
I'm writing a small function to alter a graph in a certain way and was wondering if there is a formal name for the operation. The operation takes two distinct edges, injects a new node between the ...
- 171
21
votes
2
answers
819
views
Finding at least two paths of same length in a directed graph
Suppose we have a directed graph $G=(V,E)$ and two nodes $A$ and $B$.
I would like to know if there are already algorithms for calculating the following decision problem:
Are there at least two ...
- 351
3
votes
1
answer
707
views
Efficient bandwidth algorithm
Recently I sort of stumbled on a problem of finding an efficient topology given a weighted directed graph. Consider the following scenario:
Node 1 is connected to 2,3,4 at 50 Mbps. Node 1 has 100 ...
