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

learn more… | top users | synonyms

2
votes
0answers
44 views

Algorithm for optimizing graph interconnectivity

I have a partiuclar kind of graph problem and (not having a background in graph algorithms) I would like to know how this kind of problem is called in the literature and what algorithms exist for ...
0
votes
0answers
31 views

Decomposing a complete weighted graph into a binary hierarchy of well-connected components

I have a complete weighted graph representing the distances between objects. I want to split it into exactly two well-connected components (then do this operation recursively to produce the binary ...
1
vote
2answers
60 views

Rearrange a dense distance matrix to a 2x2 non-perfect block diagonal form

I have a distance matrix (square, symmetrical, non-negative, dense). I want to split the objects into two well-connected groups. Mathematically speaking, I want to group (re-arrange) the rows/columns ...
2
votes
1answer
62 views

Algorithm to equalize the area of random tessellation of various polygons

I am looking for an algorithm that I can apply for a random tessellation of polygons with different areas. The algorithm can relax the geometry of the polygons to a condition that all of them would ...
0
votes
0answers
108 views

Dijkstras algorithm-> shortes path problem

Hi i have problem understanding shortest path computation when Dijkstra’s algorithm is applied. Given the graph as depicted below the shortest path from A to G is 42 and that corresponds to ...
0
votes
0answers
27 views

eigenvalues of graph $\mathbb{Z}_m \times \mathbb{Z}_n$

I am trying to find the eigenvalues of the Laplacian for the product of two cyclic graphs $\mathbb{Z}_L \times \mathbb{Z}_M$. I took a naive approch and coded the matrix by hand: ...
3
votes
0answers
101 views

The traveling salesman problem - Using Space Renormalization

Image attached is where I am at the moment. Blue dots=points/cities, Black x's represent central points in each box that contains at least one city, and pink dots represent the midpoint of these ...
0
votes
1answer
172 views

sparse matrix format with fast row and column access

Is there an efficient storage format for general, non-symmetric sparse matrices for which one can find all non-zero entries in a given row or column in $O(d)$ time? ($d$ is the max number of non-zero ...
0
votes
0answers
27 views

a jigsaw problem: recreating a subgraph from a limited number of fragments on an original graph

Suppose I have a set of small subgraphs $A = \{G_i\}$ of an original directed acyclic graph $G$, typically $|G_i|<<|G|$, which together span the original graph $$ G = \cup G_i $$ My question ...
3
votes
1answer
65 views

Minimizing expression DAGs

Say I have an expression involving adds, subtractions, and multiplications. I know that it is safe to assume commutativity, associativity, distributivity, etc., and would like to automatically ...
2
votes
1answer
72 views

k-splittable flow problem

The maximum k-splittable s-t flow problem(MkSF) that aims to find a maximum k-splittable flow between a given source and sink node is NP-hard. We do not require the paths to be disjoint, not even ...
1
vote
0answers
52 views

Minimum path in an undirected graph with 2 kinds of edges (locked and unlocked)

Given an undirected graph with positive weights, there are 2 kinds of edges: locked edges and unlocked edges. Determination if a given edge is either locked or unlocked edge takes O(1). For given ...
3
votes
1answer
108 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 ...
9
votes
2answers
328 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 ...
2
votes
1answer
156 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 ...
0
votes
1answer
72 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.
2
votes
2answers
150 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 ...
7
votes
2answers
357 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, ...
4
votes
1answer
673 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 ...
5
votes
1answer
178 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 ...
5
votes
3answers
139 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 ...
7
votes
3answers
1k 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 ...
3
votes
1answer
135 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})$ ?
6
votes
1answer
3k 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 ...
5
votes
1answer
112 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. ...
0
votes
1answer
203 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 ...
10
votes
5answers
404 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 ...
9
votes
1answer
1k 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 ...
4
votes
1answer
102 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 ...
2
votes
2answers
1k 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 ...
4
votes
3answers
276 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)
7
votes
1answer
350 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 ...
8
votes
1answer
212 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 ...
5
votes
0answers
2k views

Two-chordless cycle extraction from a failed comparability graph recognition

I have implemented a comparability graph recognition algorithm from M.C. Golumbic's "Algorithmic graph theory and perfect graphs" book. It is hinted in Fekete, Schepers, and van der Veen's "Exact ...
3
votes
1answer
2k views

How to implement a dynamic programming solution to the 2D bitonic euclidean traveling salesman problem?

I understand that a bitonic tour crosses all vertices with one monotonic path traveling from the left most point to the right most point, then monotonically from the left most point to the right most ...