As of May 31, 2023, we have updated our Code of Conduct.

Questions tagged [graph-algorithms]

Algorithms on graphs, excluding heuristics.

286 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
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
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
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 ...
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
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
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$ ...
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
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 ...
267 views

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
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
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
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