Questions tagged [graphs]
Questions about graphs, discrete structures of nodes which are connected by edges, including trees and graphs with weighted edges.
4,708
questions
2
votes
2
answers
815
views
State machine with knowledge of prior states?
I'm attepting to model a process flow where the transition to the next state is occasionally based on not only the input to the current state, but a prior state as well.
Below is an example graph ...
user8632
9
votes
1
answer
5k
views
Data structure for storing edges of a graph
I'm currently working on my masters thesis, and it's about clustering on graphs. I'm working with an idea using ants to solve the problem. I'm currently working on the implementation and am wondering ...
- 314
2
votes
1
answer
290
views
Finding path with minimum weight
There is a river which can be considered as an infinitely long straight line with width W.
There are A piles on the river, and B types of wooden disks are available.
The location of the $i$-th pile ...
2
votes
2
answers
3k
views
Minimum cost closed walk in a graph
Is there an efficient algorithm which gives the minimum cost closed walk in an undirected graph, which visits all vertices?
Does this problem have a name? I tried to reduce this to similar problems (...
- 303
1
vote
1
answer
1k
views
Number of Combinations of Connected Bipartite Graphs
Given two sets of vertices $U$ (size $n$) and $V$ (size $m$), how many possibilities of set of edges $E$ exist that make the bipartite graph $G = (U, V, E)$ connected?
Obviously there are $2^{n m}$ ...
- 119
4
votes
1
answer
2k
views
Can the shortest simple cycle between two given nodes be found in polynomial time?
Given an undirected simple graph $G$ and two nodes $s$ and $t$, the question asks for an algorithm to find the shortest simple cycle (no edge or vertex reuse) that contains the two. As far as I know, ...
- 141
3
votes
0
answers
3k
views
Route planning in public transport application [closed]
This is a cross-post of this StackOverflow question, (I'm not aware of linking questions between StackExchange sites). You can ignore the part about programming.
I'm making a journey planner (or a ...
- 139
5
votes
1
answer
86
views
Subgraph isomorphisms: does large out-expansion imply large in-expansion?
Let $G$ be a directed graph, and $H$ a subgraph of $G$ that contains all the vertices of $G$. (In other words, $H$ is obtained by deleting some of the edges of $G$, but not any of the vertices of $G$.)...
D.W.♦
- 152k
1
vote
0
answers
81
views
What are the popular approaches to inexact attributed-subgraph matching?
Given two graphs $G_{1}(E_{G1},V_{G1})$ and $G_{2}(E_{G2},V_{G2})$, with scalar weights on the vertices, I would like to find a subgraph $H_{1}$ of $G_{1}$ that best matches some subgraph $H_{2}$ of $...
- 61
2
votes
1
answer
129
views
Electrical resistance of expander graphs
Let $G$ be a $d$-regular expander graph. What is the electrical resistance of $G$? Is it a constant independent of the number of nodes $n$ once $d$ is large enough? If not, can we give matching upper ...
- 23
1
vote
1
answer
249
views
How to find polygons overlap reign
I have an algorithmic problem.
I have a set of different polygons in the 2D space. Each polygon is represented according to its vertex representation (x and ...
- 131
4
votes
1
answer
769
views
About metric TSP instances
Christofides' 1.5-approximation considers complete graphs as inputs, and as I understand this is essential. If the input graph is not complete, how can I add new edges with suitable weights such that ...
- 143
3
votes
1
answer
3k
views
Sabatier conjectures [closed]
While I was doing
CLRS (3rd
edition), I came across this question on page 629:
Professor Sabatier conjectures the following converse of Theorem
23.1:
Let $G = (V,E)$ be a connected, undirected ...
- 491
10
votes
2
answers
2k
views
How does one efficiently produce all binary sequences with an equal number of 0's and 1's?
A binary sequence of length $n$ is just an ordered sequence $x_1,\ldots,x_n$ so that each $x_j$ is either $0$ or $1$. In order to generate all such binary sequences, one can use the obvious binary ...
- 203
-1
votes
1
answer
198
views
Minimum path in an undirected graph with 2 kinds of edges
Given an undirected graph with positive weights, there are 2 kinds of edges: locked edges and unlocked edges.
Determination if a given edge is either locked or unlocked edge takes O(1).
For given ...
- 1
3
votes
1
answer
412
views
What is the proper runtime for visiting all outgoing edges in an adjacency list?
Suppose that we have a directed graph $G = (V, E)$ represented as an adjacency list. Suppose that we want to list all of the edges incident to some node $v \in V$. We can do this by iterating over ...
- 9,007
1
vote
1
answer
2k
views
r-regular graph and hamiltonian path
I am having some issues proving a problem I am working on. I have been sketching out examples but the proof is not jumping out at me.
Question:
Let $G = (V,E)$ be an undirected $r$-regular graph (...
- 467
2
votes
1
answer
740
views
Upper bound on the number of edges relative to the height of a DFS tree
Let $T$ be a depth-first search tree of a connected undirected graph $G$ and $h$ be the height of $T$. How do you show that $G$ has no more than $h \times |V|$ edges where $|V|$ is the number of ...
- 287
4
votes
1
answer
80
views
Is there a name for this kind of graph?
Is there a name for the DAG obtained from a directed graph by collapsing together the strongly connected components?
- 43
9
votes
1
answer
2k
views
Find which vertices to delete from graph to get smallest largest component
Given a graph $G = (V, E)$, find $k$ vertices $\{v^*_1,\dots,v^*_k\}$, which removal would result in a graph with smallest largest component.
I assume for large $n = |V|$ and large $k$ the problem ...
- 193
2
votes
1
answer
331
views
Minimum number of vertices to remove to bound the largest connected component of a graph
I have this problem, maybe anybody could help.
Given a graph $G = (V, E)$ and an integer $k \geq 1$, find the minimum number $l$ of vertices to remove to make the largest connected component of $G \...
- 193
5
votes
2
answers
3k
views
How is a hypergraph different from a bipartite graph?
How is a hypergraph different from the bipartite graph generated from the hypergraph by introducing new vertices for each hyperedge, and connecting these vertices with the vertices connected by the ...
- 5,342
3
votes
1
answer
6k
views
Get nodes that are participating in any cycle in a graph
I have a problem that states the following :
Given a cyclic graph , output for each node if the node removes all cycles in the graph.
The most trivial way to do this is using a Union-find disjoint ...
- 231
1
vote
0
answers
71
views
How to cluster nodes based on the number of dependencies
I have a problem where, there are a set of nodes and dependencies between them. I want to cluster them based on the maximum number of dependencies. Dependencies can be thought of as number of edges ...
- 2,161
1
vote
0
answers
158
views
Library for Maximum independent set on a sparse bipartite graph (from sparse matrix)
I am working with sparse matrices (not particularly huge, <100Mb) and I want to compute the largest independent set on the bipartite graph $(N,E)$ defined as follows: suppose the matrix is named $A$...
- 131
2
votes
1
answer
1k
views
How to perform alphabetically ordered DFS?
I've been working on this graph and just completely botching it. I mean to say that my solution may be the worst possible other than if a monkey had thrown darts at the graph to decide the next path. ...
- 209
2
votes
1
answer
3k
views
Find the number of topological sorts in a tree
Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.
I've tried thinking what would be the best for m to define it but couldn't get ...
- 63
9
votes
1
answer
10k
views
Effect of increasing the capacity of an edge in a flow network with known max flow
I need your help with an exercise on Ford-Fulkerson.
Suppose you are given a flow network with capacities $(G,s,t)$ and you are also given the max flow $|f|$ in advance.
Now suppose you are given an ...
- 237
0
votes
2
answers
1k
views
Worst case scenario in binary search tree retrieval
Well, i have a binary search tree $T$ that is equilibrated by height witch has $2^d+c$ nodes ($c<2^d$).
What is the number of comparisons that will occur in the worst case scenario, if we ask ...
Mihai Alin
1
vote
0
answers
95
views
Proving that a BST with N>=1 nodes will have log(N+1) levels
I am trying to prove by induction the following theorem:
Use Induction to prove the following fact: for every integer, $N\ge 1$ , a BST with $N$ nodes must have at least $\log( N + 1)$ levels.
I've ...
- 11
4
votes
2
answers
357
views
Efficiently checking if two star graphs are disjoint
I have given an undirected graph $G$ with vertex $\{1, ... n\}$ and two star subgraphs $S_1$ and $S_2$, always consisting of ALL neighbors of a given vertex, and the goal is to check wether the two ...
- 41
1
vote
3
answers
5k
views
Why is the node with the greatest DFS post-order number not necessarily a sink?
A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not ...
- 1,587
1
vote
1
answer
90
views
For Djikstra's algorithm, why are we surely done if we update all edges $|V|-1$ times?
Apparently, if we use Djikstra's algorithm to find the shortest path between the root node and all other nodes in a weighted graph with no negative cycles, we are done after updating the distance of ...
- 1,587
3
votes
1
answer
668
views
Coordinated Attack Problem On The Arbitrary Graph
Let consider a general version of Two Generals' Problem, when there are $n$ generals located on the arbitrary graph and they should agree on exactly the same value whether to attack or not to attack. ...
- 3,139
4
votes
2
answers
3k
views
Max-Flow: Detect if a given edge is found in some Min-Cut
Given a network $G=(V,E)$ , a max flow f and an edge $e \in E$ , I need to find an efficient algorithm in order to detect whether there is some min cut which contains $e$.
Another question is, how do ...
- 293
1
vote
1
answer
905
views
Trouble understanding this dynamic programming solution
Here is the question:
I have a given tree with n nodes. The task is to find the number of subtrees of the given tree with outgoing edges to its complement less than or equal to a given number K.
for ...
- 329
-2
votes
1
answer
462
views
Find the weight of the lightest path from u to v
Find the weight of the lightest path from u to v the goes through node a or/and b.
Do you have a suggestion on how it can be done?
- 5
-2
votes
3
answers
2k
views
Does reachability belong to P?
Reachability is defined as follows:
a digraph $G = (V, E)$ and two vertices $v,w \in V$. Is there a directed path from $v$ to $w$ in $G$?
Is it possible to write a polynomial time algorithm for it?
...
- 2,173
7
votes
5
answers
471
views
Team construction in tri-partite graph
The government wants to create a team with one alchemist, one builder, and one computer-scientist.
In order to have good cooperation, it is important that the 3 team-members like each other.
...
- 5,894
7
votes
3
answers
4k
views
Finding all vertices on negative cycles
Given a weighted digraph, I can check whether a given vertex belongs to a negative cycle in $O(|V|\cdot|E|)$ using Bellman-Ford. But what if I need to find all vertices on negative cycles? Is there a ...
- 193
5
votes
1
answer
2k
views
Longest path in grid like graph
This was a question at SO, and I think it's very interesting, I thought about it, but I could not provide any efficient algorithm neither showing the NP-Hardness:
Find the length of the longest non-...
user742
2
votes
1
answer
176
views
Is there a program to solve a metric TSP for 80 edges at optimum?
i'm going to use the Christofides heuristic algorithm in order to solve a TSP for about 80 edges. Eventually i should have a solution, that is within the factor 1.5 of the optimum.
But when i'm ...
- 251
3
votes
3
answers
2k
views
Shortest path with odd weight
Let G be a directed graph with non-negative weights. We call a path between two vertices an "odd path" if its weight is odd.
We are looking for an algorithm for finding the weight of the shortest odd ...
- 135
11
votes
2
answers
513
views
Longest cycle contained in two cycles
Is the following problem NP-complete? (I assume yes).
Input: $k \in \mathbb{N},G=(V,E)$ an undirected graph where the edge set can be decomposed into two edge-disjoint simple cycles (these are not a ...
- 205
2
votes
0
answers
184
views
Graph estimation in high dimensional data
I am trying to estimate the graph in very high dimensional data, I mean with million nodes. Up to now all the papers that I have found, they are limited to few thousands.
All of them like graphical ...
- 269
2
votes
3
answers
4k
views
In flow networks, may source/sink have incoming/outgoing edges?
I was wondering. May the source and sink have in-out going edges in a flow-network, and if so - does Ford-Fulkerson and the max-flow min-cut theorem apply ?
Flow-networks are always pictures with no ...
4
votes
1
answer
11k
views
Finding the path of a negative weight cycle using Bellman-Ford
I wrote a program which implements Bellman-Ford, and identifies when negative weight cycles are present in a graph. However what I'm actually interested in, is given some starting vertex and a graph, ...
2
votes
1
answer
287
views
Shortest paths candidate
Let $G = (V,E)$ be a directed graph with a weight function $w$ such that there are no negative-weight cycles, and let $v \in V$ be a vertex such that there is a path from $v$ to every other vertex. ...
- 135
3
votes
1
answer
95
views
Proof that fast broadcasts have to target larger cycles first
I am having trouble trying to formulate a simple proof. I can clearly see that what I am trying to prove is correct but to prove it I am not sure what to do.
The problem is a broadcasting problem on ...
- 467
15
votes
4
answers
11k
views
Graph Has Two / Three Different Minimal Spanning Trees?
I'm trying to find an efficient method of detecting whether a given graph G has two different minimal spanning trees. I'm also trying to find a method to check whether it has 3 different minimal ...
- 293