We’re rewarding the question askers & reputations are being recalculated! Read more.

Questions tagged [graph-theory]

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

Filter by
Sorted by
Tagged with
14
votes
6answers
978 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 ...
13
votes
6answers
4k views

What is a common file/data format for a mesh (for FEM)?

I'm developing an FEM simulation. For early testing, I will use simple self-written mesher and visualisation of the mesh graph. But I want to prepare my program to use data generated by an existing ...
11
votes
3answers
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 ...
11
votes
3answers
817 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 ...
11
votes
1answer
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 ...
8
votes
1answer
688 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
609 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 ...
7
votes
2answers
909 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, ...
6
votes
1answer
7k 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 ...
6
votes
1answer
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 ...
5
votes
3answers
186 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 ...
5
votes
1answer
703 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
1answer
70 views

Optimal partitioning of a graph

Consider a planar graph, where each node is associated with a weight. I would like to partition the graph such that the sum of the node weights in each group satisfy a minimum requirement. However, I ...
5
votes
1answer
160 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. ...
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 ...
4
votes
3answers
341 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)
4
votes
2answers
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 ...
4
votes
2answers
200 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 ...
4
votes
3answers
576 views

Minimization of non-linear function

Problem Summary I am trying to estimate the (x,y) coordinates of each node in a graph, where I know the distances between connected nodes. For example Given this ...
4
votes
0answers
81 views

Graph optimization for parallel processing

Consider the following example structure of overlapping images marked A,B,C,D. The possible overlaps are marked by gray color: The structure can be represented by a weighted undirected graph (images ...
4
votes
1answer
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 ...
4
votes
1answer
181 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 ...
3
votes
2answers
625 views

How to calculate efficiently mesh edges midpoints?

I have a 2D mesh of triangles used in Finite Element method to discretize the domain. I want to calculate the midpoints of all the edges because I want to use $\mathbb{P}^2$ elements. I am using ...
3
votes
2answers
97 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 ...
3
votes
1answer
152 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})$ ?
3
votes
1answer
39 views

Software for finding a minimum vertex cover for a hypergraph

A hypergraph $H = (V,E)$ consists of a finite set of vertices, say $V=\{1, \dots, n\}$ and a set of hyperedges $E \subseteq \mathcal{P}(V)$. We call $H$ a $k$-hypergraph if all $|e| = k$ for all $e\in ...
3
votes
1answer
104 views

Sparse Matrix Reordering

Matrix reorderings are important for many direct solvers. Sometimes the objective is to reduce the bandwith or the generated fill in by LU Decomposition. I am interested in a reordering which reduces ...
3
votes
1answer
68 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 ...
3
votes
1answer
251 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 ...
3
votes
0answers
106 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 ...
3
votes
0answers
67 views

Absorbing BC's / PML on a graph

The wave equation, $$\ddot{u} = c^2 \Delta u,$$ can be generalized to abstract graphs by using the negative graph Laplacian in place of the physical Laplacian. Is there a graph-theoretic analog of ...
3
votes
0answers
128 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 ...
2
votes
2answers
165 views

Find connected circles

I have a problem as follows: We have a set of circles (we know the radius r and the center point c in Rd of each circle) We ...
2
votes
1answer
84 views

graph theory operations to explore structure of a graph

I'm analyzing experimental data, and I've produced graphs that look similar to the attached sketch. When I look at the graph, I see structure in the connections (connections tend to be local, there is ...
2
votes
1answer
194 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 ...
2
votes
2answers
414 views

PageRank using Inverse Iteration Method by Cleve Moler

I was trying to understand how to use the inverse interation method to compute the page rank as an exercise. In this chapter (page 4) about page rank (by Cleve Moler), the author suggests to use the ...
2
votes
2answers
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 ...
2
votes
1answer
107 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 ...
2
votes
1answer
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 ...
2
votes
2answers
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 ...
2
votes
0answers
89 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 ...
1
vote
1answer
1k views

Efficient way to compute the cumulative weights of all subtrees rooted at each node in a tree?

I have a tree data structure (rooted, unbalanced, with unbounded branching factor), where each individual node has an associated 'weight'. For every node $n$ in the tree, I'd like to compute the ...
1
vote
1answer
64 views

Finding Common Side of Triangle

Given a triangulation (geometry), are there known algorithm in finding common side of triangles, that is O(N) or better?
1
vote
1answer
31 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 ...
1
vote
1answer
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 ...
1
vote
1answer
80 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 ...
1
vote
1answer
63 views

Does the box-covering algorithm work also for directed graphs?

According to this article from Wikipedia, the box-covering algorithm calculates the fractal dimension of a graph. The algorithm is based on the concept of distance between nodes; see for example the ...
1
vote
1answer
124 views

Measure the differences in vertices density in a graph?

Lets say in Graph $G$ we have two vertices $v$ and $u$, each vertex is connected to several neighbors by edges describing the distances $d_{ij}$ from these neighbors. The neighbors themselves are also ...
1
vote
1answer
671 views

Graph drawing with constraints

I have a (cyclic undirected) graph stored in a suitable structure (which depends on the language chosen). Nodes represent places in the real world and edges represent connection between them, so I ...
1
vote
2answers
152 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 ...