2.8k citations
- Max Planck SocietyDE261 papers
- Saarland UniversityDE124 papers
- Technische Universität BerlinDE55 papers
- Centre National de la Recherche ScientifiqueFR41 papers
- Korea UniversityKR41 papers
- Stanford UniversityUS25 papers
- Institut national de recherche en sciences et technologies du numériqueFR24 papers
- ETH ZurichCH21 papers
- Helmholtz Center for Information SecurityDE20 papers
- Technical University of MunichDE20 papers
- Université de LorraineFR17 papers
- University of LuxembourgLU16 papers
11 papers · 2 filters
Two Results on Slime Mold Computations
Ruben Becker, Vincenzo Bonifaci, Andreas Karrenbauer +2
We present two results on slime mold computations. In wet-lab experiments (Nature'00) by Nakagaki et al. the slime mold Physarum polycephalum demonstrated its ability to solve shor…
A Sublinear Tester for Outerplanarity (and Other Forbidden Minors) With One-Sided Error
Hendrik Fichtenberger, Reut Levi, Yadu Vasudev +1
We consider one-sided error property testing of -minor freeness in bounded-degree graphs for any finite family of graphs that contains a minor of $K_{2,k…
A Tight Analysis of the Parallel Undecided-State Dynamics with Two Colors
Andrea E. F. Clementi, Luciano Gualà, Francesco Pasquale +3
The \emph{Undecided-State Dynamics} is a well-known protocol for distributed consensus. We analyze it in the parallel \pull\ communication model on the complete graph for the \emph…
Satiation in Fisher Markets and Approximation of Nash Social Welfare
Jugal Garg, Martin Hoefer, Kurt Mehlhorn
We study linear Fisher markets with satiation. In these markets, sellers have earning limits and buyers have utility limits. Beyond natural applications in economics, these markets…
A Note on Hardness of Diameter Approximation
Karl Bringmann, Sebastian Krinninger
We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, rounds are necessary to compute the diameter [Fri…
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with nodes and edges. This problem has a long history in combinatorial optim…