# Questions tagged [graph-theory]

A field of combinatorics relating to the study of vertices and the edges that connect them

69 questions
Filter by
Sorted by
Tagged with
10 views

### polylog implementation of fully-dynamic graph connected-components?

I have read about papers in the last 20 years that have solved this problem. Many are mentioned in http://jamiemorgenstern.com/teaching/s18-6550/notes/notes-lec4-dgc.pdf Unfortunately the only ...
39 views

### How can I determine if there is a closed-loop path in a graph?

Assuming I have a computer representation of a graph presented in the figure below: How can I find out whether there are some close-loops inside the graph, like the one marked in red (or more ...
98 views

### Find shortest path around a cylinder represented by 3d triangular mesh

Suppose I have a 3d triangular mesh with the topology of a finite cylinder. Let $C$ be a vertex on that mesh. How can I find the shortest path from $C$ to itself that goes around the cylinder? By ...
21 views

### Controllability - Maximum Matching

I found this image on wikipedia referring to Barabasi's work on Network Controllability. I tried to verify it. We have a A matrix of dimensions (20 by 20) made as the image suggests. According to the '...
17 views

### Find all recurring subgraphs/patterns of maximal size in a single undirected, labeled, connected graph

I would like to identify all subgraphs of maximal size (maximum number of nodes) that are recurrent in a single undirected, labeled, connected graph. I provide exemples of input and expected output ...
116 views

### Efficient algorithm to decide if a graph is a cactus?

A cactus is a connected graph in which every edge belongs to at most one simple cycle. How should one modify the Depth First Search algorithm to obtain an efficient algorithm that determines if a ...
119 views

### Finding a shortest path in a graph

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
51 views

### Vehicle Route assignment with capacity constraint

Problem Background I'm trying to find a solution/model to the following problem: Let's consider a cellular network (mobile network, ie., hexagonal cells) denoted $N$ composed of $|N|$ cells. Each ...
227 views

### How to reorder/cluster adjacency matrix to maximize the interaction along the super diagonal?

I have the following code which takes a DataFrame and plot the pdist matrix. ...
110 views

### Factorize laplacian in terms of first derivative matrix

I am trying to factorize the following Laplacian matrix in terms of $D^TD$, D is the first derivative matrix. The tridiagonal form of the secon derivative matrix using Neumann boundary condition is ...
80 views

### Splittable and non-splittable flows in the network flow problem

I am working on a multi-commodity flow problem where for a graph $G=(V, E)$, some flows are permitted to be split and some flows should strictly follow one path. I have formulated this problem as ...
227 views

### Moore-Penrose pseudoinverse of singular rank degenerate matrix

I am trying to attain the Moore-Penrose pseudoinverse of a very large, very sparse, rank-degenerate, singular, and square matrix. ($75000 \times 75000$, near rank). The matrix is a graph Laplacian and ...
41 views