Questions tagged [graph-theory]
A field of combinatorics relating to the study of vertices and the edges that connect them
2
votes
0answers
64 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
1answer
69 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 ...
3
votes
2answers
101 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 ...
3
votes
1answer
33 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 ...
0
votes
0answers
35 views
Finding subgraphs of a given size with a fixed number of boundary edges
I have a graph, with $\sim \mathcal{O}(1000)$ verticies that has the topology of $S_{4}$, but with degenerate edges; that is, there can be multiple edges between two vertices. There are no loops, and ...
2
votes
2answers
99 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 ...
0
votes
1answer
139 views
Hypergraph matching -> adjacency matrix?
I need to do a matching on a hypergraph. I read that in the case of a hypergraph there is no adjacency matrix.
How do I represent edges then?
0
votes
1answer
55 views
simple and fast graph-clustering for paralelization of finite element simulations
I'm learning to use OpenCL to optimize some of my simulations. I realized that I need some sort of Graph-clustering or graph-partitioning to exploit efficiently local memory for un-ordered meshes.
...
1
vote
0answers
127 views
First approximation to the TSP in a non-complete Graph
I'm trying to solve the Travelling Salesman Problem in a non-complete graph $(G,E)$ using genetic algorithms.
My problem is that I can't find a good first approximation by the usual greedy algorithms,...
1
vote
1answer
156 views
Efficiently generate a random subgraph (Gs) with maximum degree K, using only edges from an existing graph G
I am looking find a way of efficiently generating a random, undirected subgraph $G_s$ with $N$ vertices, using a subset of edges from an exisiting undirected graph $G$, also of size $N$, where the ...
0
votes
1answer
411 views
Can a Depth first traversal of a graph visit node more than once? [closed]
Is there a way in which Depth First Traversal will put a node into the stack more than once using the general algorithm as shown here.
Also, is it compulsory for all nodes to be entered into the ...
1
vote
1answer
59 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 ...
3
votes
2answers
316 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 ...
1
vote
0answers
24 views
Chinese character component-based layout engine algorithms [closed]
I am looking for a PDF describing Chinese character component-based layout engine algorithms. These should allow for recursive encodings of radical and non-radical components, and the encodings should ...
1
vote
0answers
102 views
Updating factorization of Laplacian (add/remove edges)
For a graph $G=(V,E)$, recall that the unweighted Laplacian is $L:=D^\top D$, where $D\in\{-1,0,1\}^{|E|\times|V|}$ is the graph "gradient" operator that subtracts adjacent vertex values onto edges.
...
14
votes
6answers
3k 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 ...
1
vote
0answers
38 views
Alternative to two “for” loops in finding best neighborhoods for TSP?
I am trying to solve Travelling Salesman Problems using tabu search. I have been able to successfully find "near enough" optimal solutions (as well as one optimal, yay!).
For the moment I am using ...
1
vote
0answers
35 views
Interior nodes of a closed graph?
Does anybody know if any graph partitioner library such as Metis, Scotch, or Zoltan can (besides splitting a domain), differentiate between internal (i) and boundary (b) nodes?
5
votes
1answer
63 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 ...
3
votes
1answer
98 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
0answers
67 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
3answers
468 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 ...
1
vote
1answer
110 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 ...
3
votes
2answers
511 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 ...
1
vote
1answer
61 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?
0
votes
1answer
125 views
how to partition a graph(matrix) into subdomains with different sizes
i am studying the solver for PageRank problems which drived from the web link graph.
I have tried using METIS to divided the matrix into subdomains, but METIS can only produce subdomains with nearly ...
3
votes
0answers
66 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 ...
1
vote
1answer
576 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 ...
0
votes
2answers
321 views
How to represent molecules and compare equality
I originally asked this question at StackOverflow, and was suggested to bring it here.
I've seen this question about the representation of molecules in memory, and it makes sense to me (tl;dr ...
2
votes
1answer
79 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 ...
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 ...
2
votes
0answers
74 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
2answers
136 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
176 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 ...
3
votes
0answers
126 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
573 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 ...
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 ...
2
votes
1answer
106 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
61 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
239 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
703 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
509 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
85 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
174 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
809 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
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 ...
5
votes
1answer
658 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
179 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 ...
10
votes
3answers
5k 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
150 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})$ ?
