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
9 votes
2 answers
2k views

Is there an algorithm or graph theory that allows me to not need to store an intermediate matrix when calculating AT*Y1*A + BT*Y2*B?

I have a system of conductors for which there are two dense matrices of the (complex) mutual admittances, $Y_A$ and $Y_B$, which are symmetric. Then, an equivalent nodal admittance matrix $Y_N$ is ...
user avatar
0 votes
0 answers
25 views

Formal specification (and algorithm) for coarsening of bipartite graph when nodes have identical connections

Apologies for lack of precise terminology. Not sure if this is a graph replications, coarsening, covering, or something totally different. The goal of this question is to (1) formally define this ...
user avatar
  • 368
2 votes
1 answer
106 views

Bounds for the optimal bandwidth of 2D/3D FEM stiffness matrices

is anyone here aware of whether there exist bounds on the optimal bandwidths of 2D/3D FEM stiffness matrices? Edit: more specifically, I would like to have bounds on the minimum bandwidth after ...
user avatar
  • 81
0 votes
1 answer
789 views

How can I find the maximum equal-split flow of a network

I am working on a program currently that works out the maximum flow through a network using the Ford-Fulkerson algorithm, and that works fine, however, I need the final flow to meet the constraint ...
user avatar
0 votes
0 answers
77 views

How to distinguish primary hosts (stars) and orbiting satellites (planets) and tertiary bodies (moons) by their mass and trajectory?

I posted this question in the astronomy stackexchange. There are no responses, and it was suggested that I pose the question here. The "too long, didn't read" was taken from a comment, and ...
user avatar
  • 11
2 votes
0 answers
90 views

Mesh partitioning with METIS

I am trying to use METIS-5.1.0 edition in order to partion a FE mesh. For demostration purposes I created 2x2 rectangle mesh and tried to partition it. However, I notice a weird behaviour in my code. ...
user avatar
  • 471
0 votes
1 answer
28 views

Does computing all shortest paths in a simple graph result in a complete graph that follows a metric?

I have a simple graph $G=(V,E)$ that is not necessarily a complete graph. If I compute the shortest distance between every pair of vertices (let say with Floyd-Warshall algorithm) I get a complete ...
user avatar
2 votes
1 answer
128 views

Developing a meshfree contouring algorithm

I would like to find the contours of a scalar function $u(x,y)$ available as a discrete set of function values $u_i = u(x_i,y_i)$ over a scattered set of points $(x_i,y_i), i=1,...,N$. In my case, the ...
user avatar
  • 190
0 votes
0 answers
135 views

How to make a directed graph symmetric?

Say I have a directed graph given as an adjacency matrix $A$ in CSR format represented by the arrays ia (row indexes) and ja (...
user avatar
  • 190
0 votes
0 answers
29 views

Benchmark instances for directed 3-Cycle cover

The directed 3-Cycle cover asks for a vertex-covering set of oriented cycles with at least three vertices per cycle such that every vertex is covered by exactly one cycle. I have scrutinzed the ...
user avatar
1 vote
0 answers
47 views

Is there some algorithm to find the shortest path in the context of genetics and breeding?

In genetics and breeding, we typically have two parent genotype (may or may not be the same) which can produce a set of offspring with certain probability (assuming simple Mendelian inheritance). I ...
user avatar
  • 11
1 vote
1 answer
80 views

Newman algorithm yielding different result to what is given in his paper

Summary I am trying to implement Newman's algorithm for community detection, outlined in this paper. I am testing my implementation against one of the datasets used in that paper to benchmark the ...
user avatar
4 votes
1 answer
250 views

Which optimization method can be used to do the following?

I've the following system of equations for studying information flow in the below graph, $$ \frac{d \phi}{dt} = -M^TDM\phi + \text{noise effects} \hspace{1cm} (1)$$ Here, M is the incidence ...
user avatar
  • 445
0 votes
2 answers
131 views

What is an instance (precisely) in computational complexity?

I am trying to understand the notion of reduction of a problem to another problem. As it is known this has huge impact on classifying the complexity of a problem. The definition of reduction involves ...
user avatar
  • 119
1 vote
0 answers
20 views

polylog implementation of fully-dynamic graph connected-components?

I have read about papers in the last 20 years that have solved this problem. Many are mentioned in http://jamiemorgenstern.com/teaching/s18-6550/notes/notes-lec4-dgc.pdf Unfortunately the only ...
user avatar
2 votes
1 answer
1k 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 ...
user avatar
  • 123
3 votes
2 answers
179 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 ...
user avatar
  • 243
1 vote
0 answers
25 views

Find all recurring subgraphs/patterns of maximal size in a single undirected, labeled, connected graph

I would like to identify all subgraphs of maximal size (maximum number of nodes) that are recurrent in a single undirected, labeled, connected graph. I provide exemples of input and expected output ...
user avatar
6 votes
2 answers
393 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 ...
user avatar
0 votes
1 answer
298 views

Finding a shortest path in a graph

If each edge of a graph $G$ is unweighted or has equal weights, then the shortest path between two nodes in that graph is the path that contains the fewest number of edges. Such a path can be obtained ...
user avatar
  • 1
1 vote
1 answer
56 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 ...
user avatar
0 votes
1 answer
1k views

How to reorder/cluster adjacency matrix to maximize the interaction along the super diagonal?

I have the following code which takes a DataFrame and plot the pdist matrix. ...
user avatar
  • 151
3 votes
0 answers
198 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 ...
user avatar
  • 445
1 vote
1 answer
212 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 ...
user avatar
  • 13
4 votes
2 answers
479 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 ...
user avatar
  • 143
3 votes
1 answer
182 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 ...
user avatar
  • 133
2 votes
2 answers
422 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 ...
user avatar
0 votes
1 answer
425 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?
user avatar
  • 133
0 votes
1 answer
70 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. ...
user avatar
1 vote
0 answers
376 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,...
user avatar
  • 11
4 votes
1 answer
334 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 ...
user avatar
  • 41
0 votes
1 answer
2k 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 ...
user avatar
  • 103
1 vote
1 answer
81 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 ...
user avatar
2 votes
2 answers
716 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 ...
user avatar
1 vote
0 answers
28 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 ...
user avatar
1 vote
0 answers
162 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. ...
user avatar
13 votes
6 answers
6k 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 ...
user avatar
  • 1,443
1 vote
0 answers
49 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 ...
user avatar
1 vote
0 answers
47 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?
user avatar
  • 21
5 votes
1 answer
82 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 ...
user avatar
  • 51
3 votes
1 answer
139 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 ...
user avatar
  • 133
5 votes
0 answers
106 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 ...
user avatar
  • 383
5 votes
3 answers
821 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 ...
user avatar
1 vote
1 answer
203 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 ...
user avatar
  • 113
3 votes
2 answers
996 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 ...
user avatar
  • 33
1 vote
1 answer
99 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?
user avatar
  • 11
0 votes
1 answer
149 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 ...
user avatar
3 votes
0 answers
75 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 ...
user avatar
  • 3,013
1 vote
1 answer
838 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 ...
user avatar
  • 113
0 votes
2 answers
431 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 ...
user avatar
  • 101