# Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

219 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
68 views

### Constructing all digraphs without repetitions

I am interested in an algorithm that allows me to construct all inequivalent (non-isomorpic) digraphs of size n with self-loops allowed. For example, the output should look like this: Even though it ...
69 views

### Sparse matrix front reducing

There is a symmetric sparse matrix with large front. This matrix is created from graph. Element with position $(i,j)$ is not zero if nodes $i$ and $j$ are connected. What algorithms can be used for ...
316 views

### Subset of a vertex set with directed edge to all other vertices

I am posting the following question due to a lacking overview of relevant algorithms. Given a directed graph $G=(V,E)$, how can you find a (minimal) subset $S$ of $V$ such that there for every vertex ...
182 views

### Finding assignment-minimum complete k-partite graph cover

Is there any work on approximation algorithms (or exact algorithms) for finding an assignment-minimum cover of an arbitrary graph using complete k-partite subgraphs? I'm assuming this problem is NP-...
352 views

### Generate TSP instances with known optimal

Is there a known (polynomial in number of nodes) algorithm to generate TSP instances with known optimal value? The idea is to be able to generating arbitrary large instances with known optimal value,...
71 views

### Nonnegative Permanent and Ellipsoidal Method

Famously, Barahona gave an algorithm for Max Cut for Graphs without K5 complete as Subfactor Graph. This was based on the Ellipsoidal Method. Finding a Max Cut is the same for Bipartite Graphs as ...
504 views

### suffix tree: about Ukkonen's algorithm

I have specific question about suffix trees. I am reading the book Algorithms on strings_trees and sequence. I cannot understand details of Ukkonen's algorithm for constructing suffix trees. Why ...
321 views

### On Vertex Coloring of Permutation Graph and Comparability Graph and 2-SAT

I have 2 questions. Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph ...
444 views

### How to detect dead ends on a board / in a graph?

Given a (2D) board of quadratic cells (movement allowed between 4-neighbours), many of which are blocked, and given a certain starting position, how can I efficiently detect dead ends, i.e. regions of ...
341 views

### Predecessor matrix storing

What is the time complexity of computing betweenness centrality if we are given the shortest path predecessor matrix of a graph? Predecessor matrix cells look like this: If node $i$ and node $j$ are ...
149 views

### A better way to cluster items

I am working on a text processer which gives out similarities between a set of strings. After weighted LCS, Levenshtein distance and double metaphone matching, I get buckets of strings such as ...
1k views

### Designing a Transport network path suggestion tool

I am working on a suggestion system to passengers on transits to take. The thing is we are formulating stations on a transport network (eg. bus transport) as nodes and route between spatially adjacent ...
18 views

### Efficient Graph Affinity Matrix Computation

I need to compute an affinity matrix for an unweighted undirected graph of related musical artists for the purposes of spectral clustering. Now, the most obvious affinity measure to use is shortest ...
36 views

### Scheduling and routing

Given: $k > 1$ sales execs, each specializing in one of 4 lines of business (LOBs), where each exec works (sales and travel) at 7.5 hours / day $n > 1$ client sites. Constraints: Each ...
153 views

### Representation suitable for reconstruction of a tree with bounded degree

I am dealing with reconstruction of molecular graphs for which unlabelled rooted trees with maximum degree 4 are fair approximations. In particular, I would like to encode a small tree (assume number ...
278 views

### Leader election algorithm in a grid

I have to write a leader election algorithm in an unoriented mesh (a grid a*b), with many initiators. Someone give me an indication to wake up each node and then make an election in the exterior ring ...
212 views

### AVL-tree T: can T be a chain (linear BST) according to the definition?

AVL-tree T: can T be a chain (linear BST) according to the definition ? The definition of an AVL-tree is as follows: A binary search tree (BST) is called an AVL-tree if for every internal node $v$ ...