# Questions tagged [graphs]

Questions about graphs, discrete structures of nodes which are connected by edges. Popular flavors are trees and networks with edge capacity.

4,305 questions
Filter by
Sorted by
Tagged with
12 views

### Maximum planar subgraph problem

Given a graph G I want to find the maximum planar subgraph which is a grid graph. (Because the nodes of this subgraph represent points on a grid). Is there any library in python for finding the ...
17 views

### Warnsdorff's rule: more errors with odd sized boards

I wrote an algorithm based on the Warnsdorff's rule to solve the knight's tour problem, where you need to create a sequence of moves of a knight on a chessboard such that the knight visits every ...
39 views

### Can this special case of Set Cover problem be solved in polynomial time?

Let $U$ be the set of elements and $S$ be the subset collections. There exists a tree $T$ that each node is corresponding to an element in $U$. And for every subset $s$ in $S$, $V(T) \bigcap s$ is a ...
143 views

### Algorithmic Problem on Trees

Given a directed, rooted tree with $n$ vertices, the height of a vertex $v$, $h[v]$ is the number of edges on the longest path from $v$ to some reachable leaf node. Give an efficient algorithm to find ...
24 views

### Cluster 3d points with constraints

I have some 3d point cloud I wish to cluster into some number of clusters. I have the probability of two points being in the same cluster given as some function of their relative locations, with the ...
3k views

### Real life examples of *zero* weight edges in graphs

The meaning of edges with zero weight in a weighted graph questions me for a long time, and I even asked a related question previously. Yet, when I recently read here a question on real life example ...
26 views

### Proof that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree

My Professor proved that every vertex in the same strongly connected component of a graph $G$ happen to appear in the same DFS tree (which is also called tree of predecessors). He proved it by ...
31 views

### Where are the region adjacency graph algorithms?

I am interested in the Region Adjacency Graph construction problem in the context of (labelled) digital images. I am surprised to find very few resources on the topic, with the notable exception of a ...
24 views

### Why is $O(nk)$ an upper bound for the $k$-gossip problem?

I am studying the $k$-gossip problem on dynamic graphs against an adaptive adversary. Essentially, we are given a set of tokens $\mathcal{T}$ which are distributed amongst the nodes such that each ...
45 views

18 views

### Control Flow Graph - How to represent returns in code

Consider the following program int someCode1(int x){ if (x < 0) return 0; else return x; Last Statement;} Last statement could be either "printf(...
55 views

### There are n cities and m possible bidirectional roads and k temple. build roads with minimum cost such that each city has access to at least 1 temple

There are n cities and m possible roads and k temples. The cost of each road is given. Build ...
64 views

### Deciding whether a given flow is unique in $O(\lvert V \rvert + \lvert E \rvert)$ time

I am stuck with the following exercise: Is it possible to decide whether a given flow $f$ is a unique mamimum flow in $O(\lvert V \rvert + \lvert E \rvert)$ time? I am not sure that this is possible....
20 views

### Partition a graph into subgraphs such that a partition contains up to X number of a particular node type

I have a DAG graph which contains two types of nodes, A and B. I am looking for a graph partitioning algorithm that can partition a graph in sub-graphs such that each sub-graph contains up to X number ...
31 views

### Resolving a dependency graph with insufficient resources to store all states

A common way to resolve a dependency graph is to compute an execution order, and then execute each stage in turn - storing and fetching the resources as necessary. In this example, when executing ...
56 views

### Algorithm to find shortest distance from source to all other vertices of graph in O(m)?

My question is for (c), as I struggle to find an algorithm that can do this in O(m) time.
124 views

### Maximum flow on a n ×n grid

I am currently dealing with a network flow problem and I am trying to find some similar solved problems to help me formulate my solution. The text is: You are the owner of a large chain of franchise ...