Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
David Coudert, Mónika Csikós, Guillaume Ducoffe, and Laurent Viennot. Practical Computation of Graph VC-Dimension. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 8:1-8:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{coudert_et_al:LIPIcs.SEA.2024.8, author = {Coudert, David and Csik\'{o}s, M\'{o}nika and Ducoffe, Guillaume and Viennot, Laurent}, title = {{Practical Computation of Graph VC-Dimension}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {8:1--8:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-325-6}, ISSN = {1868-8969}, year = {2024}, volume = {301}, editor = {Liberti, Leo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2024.8}, URN = {urn:nbn:de:0030-drops-203731}, doi = {10.4230/LIPIcs.SEA.2024.8}, annote = {Keywords: VC-dimension, graph, algorithm} }
Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Dibyayan Chakraborty, Jérémie Chalopin, Florent Foucaud, and Yann Vaxès. Isometric Path Complexity of Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 32:1-32:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{chakraborty_et_al:LIPIcs.MFCS.2023.32, author = {Chakraborty, Dibyayan and Chalopin, J\'{e}r\'{e}mie and Foucaud, Florent and Vax\`{e}s, Yann}, title = {{Isometric Path Complexity of Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.32}, URN = {urn:nbn:de:0030-drops-185666}, doi = {10.4230/LIPIcs.MFCS.2023.32}, annote = {Keywords: Shortest paths, Isometric path complexity, Hyperbolic graphs, Truemper Configurations, Outerstring graphs, Isometric Path Cover} }
Published in: LIPIcs, Volume 241, 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)
Jérémie Chalopin, Victor Chepoi, Fionn Mc Inerney, Sébastien Ratel, and Yann Vaxès. Sample Compression Schemes for Balls in Graphs. In 47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 241, pp. 31:1-31:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{chalopin_et_al:LIPIcs.MFCS.2022.31, author = {Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Mc Inerney, Fionn and Ratel, S\'{e}bastien and Vax\`{e}s, Yann}, title = {{Sample Compression Schemes for Balls in Graphs}}, booktitle = {47th International Symposium on Mathematical Foundations of Computer Science (MFCS 2022)}, pages = {31:1--31:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-256-3}, ISSN = {1868-8969}, year = {2022}, volume = {241}, editor = {Szeider, Stefan and Ganian, Robert and Silva, Alexandra}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2022.31}, URN = {urn:nbn:de:0030-drops-168298}, doi = {10.4230/LIPIcs.MFCS.2022.31}, annote = {Keywords: Proper Sample Compression Schemes, Balls, Graphs, VC-dimension} }
Published in: LIPIcs, Volume 168, 47th International Colloquium on Automata, Languages, and Programming (ICALP 2020)
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)
@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} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Jérémie Chalopin, Victor Chepoi, Shay Moran, and Manfred K. Warmuth. Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 34:1-34:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chalopin_et_al:LIPIcs.ICALP.2019.34, author = {Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Moran, Shay and Warmuth, Manfred K.}, title = {{Unlabeled Sample Compression Schemes and Corner Peelings for Ample and Maximum Classes}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {34:1--34:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-109-2}, ISSN = {1868-8969}, year = {2019}, volume = {132}, editor = {Baier, Christel and Chatzigiannakis, Ioannis and Flocchini, Paola and Leonardi, Stefano}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2019.34}, URN = {urn:nbn:de:0030-drops-106105}, doi = {10.4230/LIPIcs.ICALP.2019.34}, annote = {Keywords: VC-dimension, sample compression, Sauer-Shelah-Perles lemma, Sandwich lemma, maximum class, ample/extremal class, corner peeling, unique sink orientation} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, and Yann Vaxès. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 22:1-22:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{chalopin_et_al:LIPIcs.SoCG.2018.22, author = {Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor and Dragan, Feodor F. and Ducoffe, Guillaume and Mohammed, Abdulhakeem and Vax\`{e}s, Yann}, title = {{Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {22:1--22:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-066-8}, ISSN = {1868-8969}, year = {2018}, volume = {99}, editor = {Speckmann, Bettina and T\'{o}th, Csaba D.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.22}, URN = {urn:nbn:de:0030-drops-87356}, doi = {10.4230/LIPIcs.SoCG.2018.22}, annote = {Keywords: Gromov hyperbolicity, Graphs, Geodesic metric spaces, Approximation algorithms} }
Published in: LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)
Jérémie Chalopin and Victor Chepoi. A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. In 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 80, pp. 101:1-101:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{chalopin_et_al:LIPIcs.ICALP.2017.101, author = {Chalopin, J\'{e}r\'{e}mie and Chepoi, Victor}, title = {{A Counterexample to Thiagarajan's Conjecture on Regular Event Structures}}, booktitle = {44th International Colloquium on Automata, Languages, and Programming (ICALP 2017)}, pages = {101:1--101:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-041-5}, ISSN = {1868-8969}, year = {2017}, volume = {80}, editor = {Chatzigiannakis, Ioannis and Indyk, Piotr and Kuhn, Fabian and Muscholl, Anca}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.101}, URN = {urn:nbn:de:0030-drops-74192}, doi = {10.4230/LIPIcs.ICALP.2017.101}, annote = {Keywords: Discrete event structures, Trace automata, Median graphs and CAT(0) cube Complexes, Unfoldings and universal covers} }
Published in: LIPIcs, Volume 66, 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)
Andreas Bärtschi, Jérémie Chalopin, Shantanu Das, Yann Disser, Daniel Graf, Jan Hackfeld, and Paolo Penna. Energy-Efficient Delivery by Heterogeneous Mobile Agents. In 34th Symposium on Theoretical Aspects of Computer Science (STACS 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 66, pp. 10:1-10:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{bartschi_et_al:LIPIcs.STACS.2017.10, author = {B\"{a}rtschi, Andreas and Chalopin, J\'{e}r\'{e}mie and Das, Shantanu and Disser, Yann and Graf, Daniel and Hackfeld, Jan and Penna, Paolo}, title = {{Energy-Efficient Delivery by Heterogeneous Mobile Agents}}, booktitle = {34th Symposium on Theoretical Aspects of Computer Science (STACS 2017)}, pages = {10:1--10:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-028-6}, ISSN = {1868-8969}, year = {2017}, volume = {66}, editor = {Vollmer, Heribert and Vall\'{e}e, Brigitte}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2017.10}, URN = {urn:nbn:de:0030-drops-70233}, doi = {10.4230/LIPIcs.STACS.2017.10}, annote = {Keywords: message delivery, mobile agents, energy optimization, approximation algorithms} }
Published in: LIPIcs, Volume 9, 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)
Jeremie Chalopin, Shantanu Das, Yann Disser, Matus Mihalak, and Peter Widmayer. Telling convex from reflex allows to map a polygon. In 28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 9, pp. 153-164, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{chalopin_et_al:LIPIcs.STACS.2011.153, author = {Chalopin, Jeremie and Das, Shantanu and Disser, Yann and Mihalak, Matus and Widmayer, Peter}, title = {{Telling convex from reflex allows to map a polygon}}, booktitle = {28th International Symposium on Theoretical Aspects of Computer Science (STACS 2011)}, pages = {153--164}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-25-5}, ISSN = {1868-8969}, year = {2011}, volume = {9}, editor = {Schwentick, Thomas and D\"{u}rr, Christoph}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2011.153}, URN = {urn:nbn:de:0030-drops-30077}, doi = {10.4230/LIPIcs.STACS.2011.153}, annote = {Keywords: polygon mapping, map construction, autonomous agent, simple robot, visibility graph reconstruction} }