# Questions tagged [graph-theory]

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

87 questions
Filter by
Sorted by
Tagged with
22 views

### Help with inferring Network topology from Spectral templates

I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the ...
179 views

### Problems on the algebraic theory of sparse matrices

I have finished testing basic large densely parallel matrix multiplication on 4 gpu's ,and have done work on TSLU and TSQR on cpu's based on mpi. I am going to continue working on the theory of ...
22 views

### Code to list all maximal bicliques of a bipartite graph

We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
28 views

### What do the Max-Cut algorithm graph cuts mean?

The max-cut algorithm divides a graph into 2 subsets, for instance: While I understand the algorithm, I do not quite understand the meaning of the result. In the above picture, what does the ...
17 views

### What is the upper bound of the size of the neighborhood of a vertex in a twin-free $K_{1,5}$-free interval graph?

Suppose that I have an interval graph that does not contian $K_{1,5}$ (the star on 6 vertices) as an induced subgraph and that I only care about twin-free graphs, i.e., no two vertices have the same ...
1 vote
47 views

### Vehicle passenger assignment with capacity constraint

Problem Background I'm trying to find a solution to the following passenger matching problem: The network is represented by graph $G=(V,E)$. $V$ is the set of nodes/stations. $p_{ij}$ is the profit of ...
12 views

### Non-Temporal Weighted Graph Datasets

I am searching for datasets to evaluate an algorithm designed for tasks such as node-classification (edge-prediction, etc.) on weighted and potentially directed graphs. The Stanford Network Analysis ...
2k views

### Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?

I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
163 views

### Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices

is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices? Edit: more specifically, I would like to have bounds on the minimum bandwidth after ...
1 vote
845 views

### How can I find the maximum equal-split flow of a network

I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint ...
79 views

### How to distinguish primary hosts (stars) and orbiting satellites (planets) and tertiary bodies (moons) by their mass and trajectory?

I posted this question in the astronomy stackexchange. There are no responses, and it was suggested that I pose the question here. The "too long, didn't read" was taken from a comment, and ...
327 views

### Mesh partitioning with METIS

I am trying to use METIS-5.1.0 edition in order to partion a FE mesh. For demostration purposes I created 2x2 rectangle mesh and tried to partition it. However, I notice a weird behaviour in my code. ...
30 views

### Does computing all shortest paths in a simple graph result in a complete graph that follows a metric?

I have a simple graph $G=(V,E)$ that is not necessarily a complete graph. If I compute the shortest distance between every pair of vertices (let say with Floyd-Warshall algorithm) I get a complete ...
207 views

### Developing a meshfree contouring algorithm

I would like to find the contours of a scalar function $u(x,y)$ available as a discrete set of function values $u_i = u(x_i,y_i)$ over a scattered set of points $(x_i,y_i), i=1,...,N$. In my case, the ...
208 views

### How to make a directed graph symmetric?

Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
33 views

### Benchmark instances for directed 3-Cycle cover

The directed 3-Cycle cover asks for a vertex-covering set of oriented cycles with at least three vertices per cycle such that every vertex is covered by exactly one cycle. I have scrutinzed the ...
1 vote
49 views

### Is there some algorithm to find the shortest path in the context of genetics and breeding?

In genetics and breeding, we typically have two parent genotype (may or may not be the same) which can produce a set of offspring with certain probability (assuming simple Mendelian inheritance). I ...
1 vote
86 views

### Newman algorithm yielding different result to what is given in his paper

Summary I am trying to implement Newman's algorithm for community detection, outlined in this paper. I am testing my implementation against one of the datasets used in that paper to benchmark the ...
285 views

### Which optimization method can be used to do the following?

I've the following system of equations for studying information flow in the below graph, $$\frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$ Here, M is the incidence ...
232 views

### What is an instance (precisely) in computational complexity?

I am trying to understand the notion of reduction of a problem to another problem. As it is known this has huge impact on classifying the complexity of a problem. The definition of reduction involves ...
1 vote
26 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 ...
2k 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 ...
229 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 ...
1 vote
27 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 ...
517 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 ...
326 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 ...
1 vote
61 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 ...
2k 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. ...
318 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 ...
1 vote
279 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 ...
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 ...