Showing cs.DSShow all
3 papers · 1 filter
cs.DS2025
Minmax-Regret -Sink Location on a Dynamic Tree Network with Uniform Capacities
Mordecai J. Golin, Sai Sandeep
A dynamic flow network with uniform capacity is a graph in which at most units of flow can enter an edge in one time unit. If flow enters a vertex faster than it can le…
cs.DS2024
Better Algorithms for Constructing Minimum Cost Markov Chains and AIFV Codes
Reza Hosseini Dolatabadi, Mordedcai J. Golin, Arian Zamani
The problem of constructing optimal AIFV codes is a special case of that of constructing minimum cost Markov Chains. This paper provides the first complete proof of correctness for…
cs.DS2024
A (Weakly) Polynomial Algorithm for AIVF Coding
Reza Hosseini Dolatabadi, Mordecai J. Golin, Arian Zamani
It is possible to improve upon Tunstall coding using a collection of multiple parse trees. The best such results so far are Iwata and Yamamoto's maximum cost AIVF codes. The most e…