1 citations · 1 across the 4 of their papers we have counts for
5 papers
Two Complexity Results on Spanning-Tree Congestion Problems
Sunny Atalig, Marek Chrobak, Christoph Dürr +4
In the spanning-tree congestion problem (), we are given a graph , and the objective is to compute a spanning tree of that minimizes the maximum edge congestio…
A Refutation of Elmasry's -Time Algorithm for Single-Source Shortest Paths
Sunny Atalig, Marek Chrobak
In this note we examine the recent paper "Breaking the Bellman-Ford Shortest-Path Bound" by Amr Elmasry, where he presents an algorithm for the single-source shortest path problem…
Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths
Sunny Atalig, Alexander Hickerson, Arrdya Srivastav +2
We consider the classical single-source shortest path problem in directed weighted graphs. D.~Eppstein proved recently an lower bound for oblivious algorithms that use rel…
A Tight Threshold Bound for Search Trees with 2-way Comparisons
Sunny Atalig, Marek Chrobak
We study search trees with 2-way comparisons (2WCST's), which involve separate less-than and equal-to tests in their nodes, each test having two possible outcomes, yes and no. Thes…
Structural Properties of Search Trees with 2-way Comparisons
Sunny Atalig, Marek Chrobak, Erfan Mousavian +2
Optimal 3-way comparison search trees (3WCST's) can be computed using standard dynamic programming in time O(n^3), and this can be further improved to O(n^2) by taking advantage of…