Search Results

Documents authored by Bénéteau, Laurine


Document
Track A: Algorithms, Complexity and Games
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}
}
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail