Questions tagged [graph-algorithms]
Algorithms on graphs, excluding heuristics.
286
questions with no upvoted or accepted answers
0
votes
0
answers
73
views
Parameterized Complexity of Vertex Multicut
Let $G$ be an undirected graph, $\{(s_1,t_1),\dots,(s_k,t_k)\}$ a collection of pairs of vertices, and $p$ an integer. The Vertex Multicut problem asks if there is a set $S$ of at most $p$ vertices ...
- 95
0
votes
0
answers
57
views
Fastest algorithm to compute maximum number of boxes that can fit inside each other
Given $n$ rectangles with widths $w_1,w_2,...,w_n$ and heights $h_1, ..., h_n$. A rectangle $i$ fits inside $j$ if and only if $h_i<h_j$ and $w_i<w_j$. We are interested in the maximum $k$ such ...
- 897
0
votes
0
answers
118
views
optimization on graph edges selection
I have the below problem. I wonder if there exists a similar known class of problems (e.g., in optimization, graph theory) which I can relate my problem to, and find a similar solution there.
I am ...
- 1
0
votes
0
answers
49
views
Is there a primal-dual algorithm for the Tree Augmentation Problem or the Cactus Augmentation Problem?
The TAP problem and the CacAP problem can be seen as covering problems for the minimum cuts of a graph.
It seems like these problems would fall under the framework of network design problems (...
- 597
0
votes
0
answers
132
views
Triangle counting using approximate matrix multiplication -- suspicious paper
This paper [1] claims that for matrices with entries in $O(1)$, one can approximately multiply them in time $O(n^2 \log 1/\delta)$ to within error delta in the Frobenius norm (Theorem 1 in that paper)....
- 610
0
votes
0
answers
142
views
Comparing two graphs when starting from a single edge
Let's assume that we are given two graphs $G_1$ and $G_2$ defined by the two following nicely drawn pictures. Black numbers label the nodes, red numbers show the edge weight between the nodes.
$G_1$ ...
- 21
0
votes
0
answers
115
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 ...
- 1,177
0
votes
0
answers
105
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 ...
- 1
0
votes
0
answers
267
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)...
- 101
0
votes
0
answers
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 ...
- 1
0
votes
0
answers
140
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 ...
- 11
0
votes
0
answers
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 ...
- 111
0
votes
0
answers
164
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 ...
- 263
0
votes
0
answers
77
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 ...
- 101
0
votes
0
answers
242
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 ...
- 1,092
0
votes
0
answers
158
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 ...
- 221
0
votes
0
answers
495
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 ...
- 383
0
votes
0
answers
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 ...
- 101
0
votes
0
answers
71
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 ...
- 101
0
votes
0
answers
318
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
0
answers
198
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-...
- 916
0
votes
0
answers
76
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 ...
- 1,578
0
votes
0
answers
535
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 ...
- 135
0
votes
0
answers
326
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 ...
- 1
0
votes
0
answers
499
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
0
answers
519
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 ...
- 1
0
votes
0
answers
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
...
- 523
0
votes
1
answer
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 ...
- 101
-1
votes
0
answers
37
views
Complexity of finding a path of specific cost
What's the complexity of the following problem?
Given a weighted directed graph G, where weights are natural numbers given in binary, and a number n (also in binary), is there a path in G of cost ...
- 111
-1
votes
1
answer
84
views
Unweighted bipartite $b$-Matching
Consider the following problem, of which I am pretty certain that it is polynomially solvable.
Given some arbitrary bipartite Graph $G=(L\cup R,E)$ and some vector $b\in\mathbb{N}^{|L|}$ with $\sum_{i=...
-1
votes
1
answer
166
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 ...
- 1,281
-3
votes
1
answer
305
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 ...
- 1
-3
votes
1
answer
244
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$ ...
- 133
-3
votes
1
answer
8k
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 ...
- 111
-4
votes
1
answer
490
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:
...
- 1
-5
votes
1
answer
366
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 ...
- 10.9k