Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

219 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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-...
0
votes
0answers
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,...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
0answers
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 ...
0
votes
1answer
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 ...
-1
votes
0answers
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 ...
-1
votes
0answers
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 ...
-1
votes
1answer
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 ...
-3
votes
1answer
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 ...
-3
votes
1answer
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$ ...
-3
votes
1answer
6k views

Efficient algorithm to create a directed dependency graph

I am looking for an efficient algorithm to create a graph like this: Initially the graph is filled with x then hs then ...
-5
votes
1answer
307 views

Attacking TSP via small nonintersecting circuits

Consider the problem of finding smaller "non-intersecting" circuits or paths in graphs embedded in the euclidean plane (visiting all vertices) in the sense of geometric intersections of edges plotted ...