Questions tagged [graph-theory]
A field of combinatorics relating to the study of vertices and the edges that connect them
21
questions with no upvoted or accepted answers
5
votes
0
answers
115
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 ...
- 393
5
votes
0
answers
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 ...
- 590
3
votes
0
answers
82
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,143
3
votes
0
answers
138
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 ...
- 309
2
votes
0
answers
22
views
Code to list all maximal bicliques of a bipartite graph
We are looking for a code to list all maximal bicliques in bipartite graphs efficiently, as we want to run it on (large and sparse) graphs, with up to roughly a million nodes and edges in no more that ...
- 21
2
votes
0
answers
383
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. ...
- 481
2
votes
0
answers
114
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 ...
- 435
1
vote
0
answers
47
views
Vehicle passenger assignment with capacity constraint
Problem Background
I'm trying to find a solution to the following passenger matching problem:
The network is represented by graph $G=(V,E)$. $V$ is the set of nodes/stations. $p_{ij}$ is the profit of ...
- 11
1
vote
0
answers
50
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 ...
- 11
1
vote
0
answers
30
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 ...
- 111
1
vote
0
answers
27
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 ...
1
vote
0
answers
419
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,...
- 11
1
vote
0
answers
197
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.
...
- 1,341
1
vote
0
answers
50
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 ...
- 11
1
vote
0
answers
58
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?
- 21
0
votes
0
answers
65
views
How is kernel fusion done?
I have a computational graph (DAG) consisting of element-wise operations (potentially with broadcasting) and reshape/reduce operations (reshaping/sum/max). I'm trying to understand how vertical kernel ...
- 111
0
votes
0
answers
60
views
Help with inferring Network topology from Spectral templates
I am trying to use matlab and YALMIP to solve a graph learning problem of recovering eigenvalues from the eigenvectors of the covariance of sampled graph signal data. This is to implement the ...
0
votes
0
answers
31
views
What do the Max-Cut algorithm graph cuts mean?
The max-cut algorithm divides a graph into 2 subsets, for instance:
While I understand the algorithm, I do not quite understand the meaning of the result. In the above picture, what does the ...
- 101
0
votes
0
answers
79
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 ...
- 11
0
votes
0
answers
237
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 (...
- 607
0
votes
0
answers
36
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 ...
- 101