1 citations · 4 across the 22 of their papers we have counts for
7 papers · 1 filter
Time-Optimal APSP and Matrix Multiplication in Classes of Linear Neighborhood Complexity
Édouard Bonnet, Julien Duron, Marcin Pilipczuk +2
The notion of linear neighborhood complexity is a very general structural assumption on a graph class, covering most classes of sparse graphs such as planar graphs, graphs excludin…
A tight lower bound for malicious online bipartite matching with limited recourse budget
Julia Baligacs, Bartłomiej Bosek, Paweł Putra +2
We study one-sided online bipartite matching with recourse. In this setting, one side of a bipartite graph is known in advance, while vertices on the other side arrive online toget…
Multiway -Cut is fixed-parameter tractable
Tony Huynh, Eun Jung Kim, Sang-il Oum +2
A connectivity function on a finite set is a function that is submodular and symmetric, with . Given a connectivity function via…
An Erdős-Pósa theorem for cycles and faces of distinct lengths
J. Pascal Gollin, Maximilian Gorsky, Meike Hatzel +6
We show that for every , every graph contains vertex-disjoint cycles of different lengths, or there exists a set with $|X| \in \mathcal…
Fast decremental tree sums in forests
Benjamin Aram Berendsohn, Marek Sokołowski
We study two fundamental decremental dynamic graph problems. In both problems, we need to maintain a vertex-weighted forest of size under edge deletions, weight updates, and a…
Dynamic Detours
Daniel Dadush, Michał Pilipczuk, Amadeus Reinald +2
Fix a parameter . We give dynamic data structures that for a fully dynamic undirected graph , updated over time by edge insertions and edge deletions, can answe…
Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
Sang-il Oum, Marek Sokołowski
We study connectivity functions, that is, integer-valued symmetric submodular functions on a finite ground set attaining on the empty set. For a connectivity function on an…