21 citations · 28 across the 15 of their papers we have counts for
28 papers
FPTAS for Polygonal Multi-Robot Motion Planning
Sayan Bandyapadhyay, William Lochet, Saket Saurabh +1
We study multi-robot motion planning in a polygonal environment with polygonal robots. The setting of the problem consists of a polygonal domain with vertices and…
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +4
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most weights can be changed to form a metric. Motivated by metric…
On a tree-based variant of bandwidth and forbidding simple topological minors
Hugo Jacob, William Lochet, Christophe Paul
We obtain structure theorems for graphs excluding a fan (a path with a universal vertex) or a dipole () as a topological minor. The corresponding decompositions can be com…
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
Blow-ups and extensions of trees in tournaments
Pierre Aboulker, Frédéric Havet, William Lochet +3
A class of acyclic digraphs is linearly unavoidable if there exists a constant such that every digraph is contained in all tournaments of order…
Packing Short Cycles
Matthias Bentert, Fedor V. Fomin, Petr A. Golovach +6
Cycle packing is a fundamental problem in optimization, graph theory, and algorithms. Motivated by recent advancements in finding vertex-disjoint paths between a specified set of v…