1 citations · 1 across the 7 of their papers we have counts for
8 papers
A Gossiping Protocol for Sparse Ad-Hoc Radio Networks
Chao Wu, Marek Chrobak
We study the problem of gossiping (all-to-all information exchange) in ad-hoc radio networks. Such a network is represented by a strongly-connected directed graph with \(n\) vertic…
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…
On HTLC-Based Protocols for Multi-Party Cross-Chain Swaps
Emily Clark, Chloe Georgiou, Katelyn Poon +1
In his 2018 paper, Herlihy introduced an atomic protocol for multi-party asset swaps across different blockchains. His model represents an asset swap by a directed graph whose node…
On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
Jordan Kuschner, Yugarshi Shashwat, Sarthak Yadav +1
Selective families of sets, or selectors, are combinatorial tools used to "isolate" individual members of sets from some set family. Given a set and an element , to iso…
A Note on Local Convergence of Iterative Processes for Pipe Network Analysis
Huong Luu, Marek Chrobak
Analysis of pipe networks involves computing flow rates and pressure differences on pipe segments in the network, given the external inflow/outflow values. This analysis can be con…
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…