A new distributed algorithm for computing a minimum spanning tree (MST) in the CONGEST-KT model, where messages are limited to $O(\log n)$ bits and each vertex initially knows the identifiers of its neighbors, which breaks the quadratic time--message trade-off barrier.
Taisuke Izumi, Naoki Kitamura, T. Masuzawa· 0 citations
It is proved that \CCRCJ~on path graphs is NP-hard even on caterpillar graphs, which is a very restricted subclass of trees and chordal graphs minimally above path graphs, thereby resolving Nakahata's open problem on chordal graphs under multiset size constraints.
A randomized combinatorial algorithm that solves MSRP on unweighted directed graphs in $\tilde{O}(m\sqrt{\sigma n} + \sigma n^2)$ time, with all the output distances correct with high probability.
This paper studies local failover schemes that minimize the number of rewritable bits in the packet header on directed graphs with $k-arc failures and shows that their scheme is nearly optimal when the number of faulty arcs is approximately less than the number of nodes.
