# 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
Filter by
Sorted by
Tagged with
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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 ...
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,...
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 ...
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. ...
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 ...