Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

232 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
0
votes
0answers
84 views

NP-Hard or PTIME?

I am working on my research problem that essentially boils down to the following question. Consider an $N \times N$ matrix. There is a man at given a starting point $(x,y)$. In each unit of time, the ...
0
votes
0answers
50 views

Matching of two weighted graphs allowing one-to-many mapping

I am looking for a heuristic for a graph matching problem as follows. Given two graphs: $A$ (consisting of nodes $a_i$) and $B$ (consisting of nodes $b_i$). Typically the size of $B$ is larger than ...
0
votes
0answers
61 views

About complexity of recovering or learning Bayesian networks

Are there complexity theoretic results about recoverability or learnability of the marginals (of the source vertices) and the conditionals (along each of the edges) of a Bayesian network from having ...
0
votes
0answers
237 views

What's the fastest algorithm to compute Max{max flow with single source and multiple sinks}

Given an arbitrary directed graph(not planar, cycles included), a source node $S$ and constant constraints on edges, for each sink node $t_i$, the maximum flow from $S$ to $t_i$ is denoted by $f(S,t_i)...
0
votes
0answers
1k views

How to solve such a graph optimization problem?

I have a graph optimization problem which is hard to describe in the title. There is a component based system which consists of components and data transmissions between components(components and ...
0
votes
0answers
132 views

CSP-problem, based on context-free grammar

I'm trying to solve a CSP (Constraint-Satisfaction-Problem), which is based on arbitrary context-free grammars. A quick example: Let's say we have a context-free grammar with the following production ...
0
votes
0answers
76 views

Detect highly weighted but also densely inter-connected subnetworks

In a connected / undirected / node weighted (with both positive and negative weights) network, there are many papers studied about the 'Maximum weight connected subgraph' problem. But are there any ...
0
votes
0answers
155 views

Transitive reduction not provably minimal

Working on finding minimal equivalent graphs, which unlike transitive reductions only allows for edge removals from the original graph. I was under the impression that if you allow for new edges to be ...
0
votes
0answers
73 views

DAG reduce edges by transitivity

I have a DAG like this $G_1 = \lbrace A \to B \to C \rbrace$ My algorithm modify $G_1$ so it will be like this $ G_2 = \lbrace A \to C, B \to C \rbrace $ I now that $G_2$ is not a transitive ...
0
votes
0answers
194 views

Efficiently computing propagation values for only a few positions in a grid

Consider a matrix filled with some nodes containing positive integers ("starts"), some nodes marked as a wall, and the rest of the nodes given a value of infinity. The propogation rule is simple: For ...
0
votes
0answers
136 views

Distance oracles in trees

Given an unweighted tree $T=(V,E)$ what is the minimum number of distance oracles that allow to detect the position in the graph of every node $v$? A distance oracle is "special node" $u$ of the ...
0
votes
0answers
418 views

Rectangular constraints in Delaunay Triangulation without edges within

I'm using a triangulation library to compute the Constrained Delaunay Triangulation of a set of rectangles within some large boundary. The algorithm returns all the edges, but also adds edges inside ...
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
187 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
416 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
73 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
511 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
324 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
479 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
364 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
1answer
158 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
0answers
28 views

Algorithm to decide percentage of data from previous node, current node and forward nodes

I have a graph-like structure, let's say there is one node $C$, who has 2 predecessors $A,B$ and 1 successor $D$. I have a value of $C$. Let's say value at $C=30$%. From this, I could infer that I ...
-3
votes
1answer
282 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
213 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
7k 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 ...
-4
votes
0answers
77 views

Argument that Graph Isomorphism is polynomial via reduction to CNF

In short we found 3 invertible transformations which imply that Graph Isomorphism is polynomial. Meta reasoning: Isomorphism preserving transformation CNF to "sparse" CNF is possible and ...
-4
votes
1answer
50 views

Distinguish Graph from Tree using Adjacency Matrix

Given an adjacency matrix, is there a way to determine if the graph will be a tree or a graph (whether or not there is a cycle). For example, given the adjacency matrix: ...
-5
votes
1answer
321 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 ...

1 2 3 4
5