# Questions tagged [graph-theory]

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

73 questions
Filter by
Sorted by
Tagged with
254 views

### Optimal Scheduling of Parallel Tasks with Known Dependencies

This is maybe a trivial question, but I am stuck with the problem. Suppose we have a general graph: $$G=(V,E)$$ Each edge represents a task, each vertex represents a data for the task (hence each ...
859 views

### Testing if two 12x12 matrices have the same determinant

I am given a $12 \times 12$ matrix $Q$ that is symmetric, invertible, positive definite and dense. I need to test if $$\det(Q) = \det(12I-Q-J) \; \; (1)$$ where $J$ is the all ones matrix. I am ...
553 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 ...
93 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.
177 views

### Finding two shortest path that are 'distant' in the graph

The problem is as follows: We are given a graph with each edge length 1 and two pairs of vertices (a,b) and (c,d). How to find shortest paths between from a to b and from c to d, with assumption that ...
954 views

### Finding the distribution (histogram) of eigenvalues for large sparse matrices

Are there any existing programs that are able to compute the (approximate) distribution of eigenvalues for very large (symmetric) sparse matrices? Note that I do not need the eigenvalues themselves, ...
2k views

### Find / Detect / Enumerate all Cliques or Independent Sets

What are generally best choices for enumerating all k-cliques (or independent sets of size k)? The graphs I am looking at probably won't have more than ~ 100 nodes. Presently I code in Python with ...
722 views

### how to visualize lattice with periodic, helical, etc. boundary conditions?

I am trying to write a special hexagonal lattice generator, with several kinds of boundary conditions, such as helical BC, periodic BC, and I find it hard to verify whether it works correctly. I tried ...
189 views

### Where do I find data to start a graph data structure to practice on?

I am interested in learning firsthand about graph data structures but have no data to put into the database. Can anyone recommend a source for a beginner to find graph data? (Preferably a source that ...
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 ...
153 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})$ ?
12k 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 ...
162 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 ...
1k 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 ...
191 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 ...
352 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)
719 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 ...
641 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 ...