3 Search Results for "Bénéteau, Laurine"

Document
DOI: 10.4230/LIPIcs.FUN.2026.30
Replacing Cops with Zombies

Authors: Fengyi Liu and Avery Miller

Published in: LIPIcs, Volume 366, 13th International Conference on Fun with Algorithms (FUN 2026)

Abstract
In the Cops and Robbers game, two players take turns to move their pieces in a given graph, and the goal of the Cop player is to have any of their pieces capture the piece controlled by the Robber player. In the Zombies and Survivors variant, the Zombie player is trying to catch the piece controlled by the Survivor player, but the pursuers are more restricted: the zombie pieces must always move, and must do so toward the survivor along a shortest path. Essentially, the zombies move in a 'brainless' way, which severely limits the design of algorithmic strategies. In a practical setting where the pursuers are robots or drones, the zombie strategies can be carried out by simpler/cheaper devices. This motivates the question: when can cops be replaced by zombies? In contrast to previous work that highlights graph classes where cops are significantly more useful when trying to catch the evader, we examine some situations where the simpler restricted movements imposed on zombies can be sufficient.
Cite as

Fengyi Liu and Avery Miller. Replacing Cops with Zombies. In 13th International Conference on Fun with Algorithms (FUN 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 366, pp. 30:1-30:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{liu_et_al:LIPIcs.FUN.2026.30,
  author =	{Liu, Fengyi and Miller, Avery},
  title =	{{Replacing Cops with Zombies}},
  booktitle =	{13th International Conference on Fun with Algorithms (FUN 2026)},
  pages =	{30:1--30:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-417-8},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{366},
  editor =	{Iacono, John},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2026.30},
  URN =		{urn:nbn:de:0030-drops-257492},
  doi =		{10.4230/LIPIcs.FUN.2026.30},
  annote =	{Keywords: Pursuit-Evasion Games, Grid Graphs, Cop Number, Zombie Number, Throttling Number}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.12
Testing Whether a Subgraph Is Convex or Isometric

Authors: Sergio Cabello

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
We consider the following two algorithmic problems: given a graph G and a subgraph H ⊆ G, decide whether H is an isometric or a geodesically convex subgraph of G. It is relatively easy to see that the problems can be solved by computing the distances between all pairs of vertices. We provide a conditional lower bound showing that, for sparse graphs with n vertices and Θ(n) edges, we cannot expect to solve the problem in O(n^{2-ε}) time for any constant ε > 0. We also show that the problem can be solved in subquadratic time for planar graphs and in near-linear time for graphs of bounded treewidth. Finally, we provide a near-linear time algorithm for the setting where G is a plane graph and H is defined by a few cycles in G.
Cite as

Sergio Cabello. Testing Whether a Subgraph Is Convex or Isometric. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 12:1-12:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{cabello:LIPIcs.WADS.2025.12,
  author =	{Cabello, Sergio},
  title =	{{Testing Whether a Subgraph Is Convex or Isometric}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{12:1--12:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.12},
  URN =		{urn:nbn:de:0030-drops-242439},
  doi =		{10.4230/LIPIcs.WADS.2025.12},
  annote =	{Keywords: convex subgraph, isometric subgraph, plane graph}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2020.10
Medians in Median Graphs and Their Cube Complexes in Linear Time

Authors: Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès

Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)

Abstract
The median of a set of vertices P of a graph G is the set of all vertices x of G minimizing the sum of distances from x to all vertices of P. In this paper, we present a linear time algorithm to compute medians in median graphs, improving over the existing quadratic time algorithm. We also present a linear time algorithm to compute medians in the 𝓁₁-cube complexes associated with median graphs. Median graphs constitute the principal class of graphs investigated in metric graph theory and have a rich geometric and combinatorial structure. Our algorithm is based on the majority rule characterization of medians in median graphs and on a fast computation of parallelism classes of edges (Θ-classes or hyperplanes) via Lexicographic Breadth First Search (LexBFS). To prove the correctness of our algorithm, we show that any LexBFS ordering of the vertices of G satisfies the following fellow traveler property of independent interest: the parents of any two adjacent vertices of G are also adjacent.
Cite as

Laurine Bénéteau, Jérémie Chalopin, Victor Chepoi, and Yann Vaxès. Medians in Median Graphs and Their Cube Complexes in Linear Time. In 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 168, pp. 10:1-10:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{beneteau_et_al:LIPIcs.ICALP.2020.10,
  author =	{B\'{e}n\'{e}teau, Laurine and Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Vax\`{e}s, Yann},
  title =	{{Medians in Median Graphs and Their Cube Complexes in Linear Time}},
  booktitle =	{47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)},
  pages =	{10:1--10:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-138-2},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{168},
  editor =	{Czumaj, Artur and Dawar, Anuj and Merelli, Emanuela},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2020.10},
  URN =		{urn:nbn:de:0030-drops-124171},
  doi =		{10.4230/LIPIcs.ICALP.2020.10},
  annote =	{Keywords: Median Graph, CAT(0) Cube Complex, Median Problem, Linear Time Algorithm, LexBFS}
}
  • Refine by Type
  • 3 Document/PDF
  • 2 Document/HTML

  • Refine by Publication Year
  • 1 2026
  • 1 2025
  • 1 2020

  • Refine by Author
  • 1 Bénéteau, Laurine
  • 1 Cabello, Sergio
  • 1 Chalopin, Jérémie
  • 1 Chepoi, Victor
  • 1 Liu, Fengyi
  • Show More...

  • Refine by Series/Journal
  • 3 LIPIcs

  • Refine by Classification
  • 2 Theory of computation → Design and analysis of algorithms
  • 1 Mathematics of computing → Graph algorithms
  • 1 Mathematics of computing → Graph theory
  • 1 Theory of computation → Computational geometry

  • Refine by Keyword
  • 1 CAT(0) Cube Complex
  • 1 Cop Number
  • 1 Grid Graphs
  • 1 LexBFS
  • 1 Linear Time Algorithm
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact