The Stack Overflow podcast is back! Listen to an interview with our new CEO.

Questions tagged [graph-theory]

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

67 questions
Filter by
Sorted by
Tagged with
96 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 '...
16 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 ...
110 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 ...
117 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 ...
49 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 ...
158 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. ...
103 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 ...
77 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 ...
190 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 ...
38 views

520 views

Evolutionary algorithm - Traveling Salesman -fitness function

I'm trying to solve this problem using genetic algorithms and am having difficulty choosing the fitness function. My problem is a little different than the original Traveling Salesman Problem, since ...
87 views

Unique Partition of a Graph

Given an undirected graph, is it possible to find a criteria that leads to a unique partition of the nodes? The graph is not weighted.