Questions tagged [graph-theory]
A field of combinatorics relating to the study of vertices and the edges that connect them
14
questions with no upvoted or accepted answers
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
0answers
82 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 ...
3
votes
0answers
108 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
68 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
0answers
90 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
0answers
10 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 ...
1
vote
0answers
16 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
0answers
213 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
196 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 ...
1
vote
0answers
121 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
vote
0answers
44 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
40 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?
0
votes
0answers
21 views
Controllability - Maximum Matching
I found this image on wikipedia referring to Barabasi's work on Network Controllability.
I tried to verify it.
We have a A matrix of dimensions (20 by 20) made as the image suggests. According to the '...
