# Questions tagged [graph-theory]

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

64 questions
Filter by
Sorted by
Tagged with
6k views

### I am looking for a parallel dynamic graph library in C++

Hello scicomp community, I have worked in the area of graph algorithms using frameworks such as NetworkX (Python), JUNG and YFiles (Java). I am now entering the area of parallel and high perfomance ...
151 views

### multiplications of graph adjacency matrix

Suppose $A$ is a directed graph adjacency matrix. Is there any good interpration of the $(i,j)-$entry of the matrix $(A^{32}\cdot (A^T)^{32})$ ?
11k views

### Concave polygon 'hull' finding

I implemented an algorithm to find the alpha shape of a set of points. The alpha shape is a concave hull for a set of points, whose shape depends on a parameter alpha deciding which points make up the ...
156 views

### Is there a way to inspect the graph of a sparse matrix with PETSc?

I am currently trying to code the CA-CG method within the PETSc framework. A mandatory step in this process is the implementation of the "matrix powers kernel" algorithm for a generic sparse matrix. ...
283 views

### Quickly computing inversion of a large sparse partial stochastic matrix

Suppose I have a sparse stochastic matrix $M$ (with thousands or millions of stochastic column vectors), possibly encoding some links in a web graph. Now I split it into two matrices: $D$ containing ...
948 views

### Approximate spectrum of a large matrix

I want to compute the spectrum (all the eigenvalues) of a large sparse matrix (hundreds of thousands of rows). This is hard. I am willing to settle for an approximation. Are there approximation ...
4k views

### Algorithms for community detection for bipartite graphs?

Are there any algorithms for community detection for bipartite graphs (2-mode networks) implemented in igraph, networkX, R or Python etc.? In particular, is there such an implementation in which one ...
179 views

### Generating lattice clusters/graphs in parallel

I'm trying to generate all graphs with n or fewer vertices that can be embedded in some lattice, eg square, triangular, Kagome. Do there exist algorithms to both enumerate and draw these graphs? What ...
2k views

### Depth of a Binary Search Tree

I wrote a function to search a Binary Search Tree, but I have logic problems: When I insert some values, and I have a tree of 2 levels, and the final level (2 in this case) is not full (full is that ...
338 views

### What is a good introduction to graph theory / algorithm

By good I mean minimal and essential. One whose concepts form a minimum spanning tree, and whose words are precious :) (A small pdf would be perfect)
669 views

### C++ library for graphs with maximum common subgraph solver

I'm looking for a convenient, free C++ library for graphs that include a solver for the maximum common subgraph (MCS) problem. I'm aware of the Boost Graph Library and LEMON , but neither includes an ...
590 views

### Where to find data sets for testing minimum vertex cover algorithm for bipartite graphs?

I'm playing with simple implementations of algorithms to find minimum vertex cover/maximum cardinality matching in bipartite graphs. However, I seem to have trouble googling for some test data sets ...