11 papers
Incremental Submodular Maximization: Better Than Greedy
Marcin Bienkowski, Joakim Blikstad, JarosÅaw Byrka +3
We consider submodular maximization under increasing cardinality constraint and ask for a good incremental solution, i.e., an ordering of the ground set such that each prefix of th…
Revisiting Diameter in Directed Graphs
Ben Bals, Joakim Blikstad, Daniel Dadush +2
The reachability diameter () of a directed graph is the maximum distance over all pairs where is reachable from . This notion is present in the def…
Greedy Algorithms for Shortcut Sets and Hopsets
Ben Bals, Joakim Blikstad, Greg Bodwin +3
For many popular graph metric sparsifiers, such as spanners, emulators, and preservers, simple and elegant greedy algorithms are known that achieve state-of-the-art or existentiall…
Deterministic Edge Coloring with few Colors in CONGEST
Joakim Blikstad, Yannic Maus, Tijn de Vos
As the main contribution of this work we present deterministic edge coloring algorithms in the CONGEST model. In particular, we present an algorithm that edge colors any -node g…
Minimum Star Partitions of Simple Polygons in Polynomial Time
Mikkel Abrahamsen, Joakim Blikstad, André Nusser +1
We devise a polynomial-time algorithm for partitioning a simple polygon into a minimum number of star-shaped polygons. The question of whether such an algorithm exists has been…
Combinatorial Maximum Flow via Weighted Push-Relabel on Shortcut Graphs
Aaron Bernstein, Joakim Blikstad, Jason Li +2
We give a combinatorial algorithm for computing exact maximum flows in directed graphs with vertices and edge capacities from in time,…