# Questions tagged [graphs]

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

3,788 questions
Filter by
Sorted by
Tagged with
2 views

### Ranking (k-best) or genetic coding for spanning arborescences

I am wondering if there is a simpler way to rank spanning arborescences or any way to code spanning arborescences genetically. According to the comment by @BearAqua in my another question, min ...
18 views

### How to build a graph of people where node connections are determined by name and age?

I was given the following question (please don't mind the programming language semantics, it's a language-agnostic question): Given a list of Pesrons, and two ...
15 views

### Time complexity for computing the highest degree vertex

Consider an undirected and unweighted graph with $n=|V|$ nodes and $m=|E|$ edges stored in adjacency matrix format. What is the time complexity of finding the highest-degree vertex, assuming the ...
32 views

### How to find a cut in a graph with additional constraints?

I have a complete undirected graph $G=(V,E)$ with positive non-null rational weights $c:E \to \mathbb{Q}^+_{*}$ on the edges, such that $c(v,v) = 0$ for all $v$, and a subset $C \subset V$. I would ...
11 views

6 views

### How to extract the buildings bottom surfaces from a large city 3D mesh?

I have a 3D mesh comprised of city buildings, no ground surface, just buildings. The goal is to extract the buildings bottom surfaces. So far I have tried to cut the mesh by a threshold computed from ...
20 views

### Kruskal naive implementation: how to use DFS to detect cycle in MST plus next edge?

Most discussion of naive (without Union-Find) implementations of Kruskal's algorithm for finding the minimal spanning tree that I see has a handwavy bit: "just use DFS to detect if there is a ...
53 views

55 views

### Data structure to determine vertex membership after edge removal from a tree in sub-linear time?

Consider a tree $T = (V,E)$ and its induced disjoint trees $T_1 = (V_1, E_1), T_2=(V_2, E_2)$ by the removal of an edge $e \in E$. Is there a data structure that enables the immediate determination of ...
15 views

### Looking for an algorithm to minimize cost of edge traversals in a bipartite graph subject to constraints

I have a set of urns that can each hold different amounts of sand. Porters can deliver sand to each urn subject to a transport fee per unit of sand. Each porter has a finite amount of sand they are ...
244 views

### efficient algorithm for min cut with specified number of vertices

Consider a graph with vertices $V$ and edges $E$. The standard version of the min cut problem is to find the partition of $V$ into a (non-empty) subset $C$ and its complement $\bar{C}$ so as to ...
50 views

### Algorithm to color the edges of the square of a cycle

It is known that any power of cycle on even vertices is in Class 1, that is, can be edge colored in $\Delta$ colors, where $\Delta$ is its maximum degree which equals twice the power. But, I wish to ...
80 views

### Google Foobar Level 4 - Graph Problem

So, I have been solving problems in Google Foobar for the past two weeks or so ans has reached Level 4. The first problem is as stated below and I have come up with a solution which is able to pass ...
52 views

### Topological sort where some nodes can't come in between two other nodes

I have a DAG which I would like to do a topological sort on but there is a catch. I also have a relation NotBetween(X,Y,Z) which means that in the sort the node Y cant come "in between" node ...
28 views

### Finding homotopies in a 2-complex

Are there any efficient algorithms to find the shortest homotopy between two paths in a $2$-complex?
45 views

### Total weight of all spanning trees

Given a weighted simple undirected connected graph $G = (V, E, w:E \to \mathbb{R})$, let $\tau(G)$ be the set of all its spanning trees. Is there an efficient algorithm to determine or estimate with ...
28 views

### Minimum spanning tree of multi directed graph

Solved. This is a minimum spanning tree problem, which can be solved efficiently by Edmonds' algorithm (or Chu–Liu/Edmonds' algorithm). I have problem of inferring a rooted tree out of a connected ...
30 views

### what would be the time complexity of DBSCAN algorithm?

what would be the time complexity of DBSCAN algorithm if we use it for graph(sparse) clustering $O(n^2)$ or $O(n \log{n})$?