# 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
Filter by
Sorted by
Tagged with
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 ... 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 ...
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 ...
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 (...
1 vote
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}$ ...
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, ...
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 ...
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$.)...
1 vote
81 views

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 ...
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 ...
1 vote
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 ...
1 vote
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$...
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. ...
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 ...
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 ...
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 ... 1 vote
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 ...
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 ...
1 vote
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 vote
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 ...
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. ...
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 ...
1 vote
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 ...
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?
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? ...
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. ...
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 ...
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-... 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 ...
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 ...
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 ...
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 ...
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 ...
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, ...
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. ...