Published in: LIPIcs, Volume 249, 17th International Symposium on Parameterized and Exact Computation (IPEC 2022)
Guillaume Ducoffe. Obstructions to Faster Diameter Computation: Asteroidal Sets. In 17th International Symposium on Parameterized and Exact Computation (IPEC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 249, pp. 10:1-10:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{ducoffe:LIPIcs.IPEC.2022.10, author = {Ducoffe, Guillaume}, title = {{Obstructions to Faster Diameter Computation: Asteroidal Sets}}, booktitle = {17th International Symposium on Parameterized and Exact Computation (IPEC 2022)}, pages = {10:1--10:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-260-0}, ISSN = {1868-8969}, year = {2022}, volume = {249}, editor = {Dell, Holger and Nederlof, Jesper}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2022.10}, URN = {urn:nbn:de:0030-drops-173668}, doi = {10.4230/LIPIcs.IPEC.2022.10}, annote = {Keywords: Diameter computation, Asteroidal number, LexBFS} }
Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)
Pierre Bergé, Guillaume Ducoffe, and Michel Habib. Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 9:1-9:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{berge_et_al:LIPIcs.STACS.2022.9, author = {Berg\'{e}, Pierre and Ducoffe, Guillaume and Habib, Michel}, title = {{Subquadratic-Time Algorithm for the Diameter and All Eccentricities on Median Graphs}}, booktitle = {39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)}, pages = {9:1--9:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-222-8}, ISSN = {1868-8969}, year = {2022}, volume = {219}, editor = {Berenbrink, Petra and Monmege, Benjamin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.9}, URN = {urn:nbn:de:0030-drops-158192}, doi = {10.4230/LIPIcs.STACS.2022.9}, annote = {Keywords: Diameter, Eccentricities, Metric graph theory, Median graphs, Hypercubes} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Guillaume Ducoffe. Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ducoffe:LIPIcs.IPEC.2021.15, author = {Ducoffe, Guillaume}, title = {{Maximum Matching in Almost Linear Time on Graphs of Bounded Clique-Width}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.15}, URN = {urn:nbn:de:0030-drops-153987}, doi = {10.4230/LIPIcs.IPEC.2021.15}, annote = {Keywords: Maximum Matching, Maximum b-matching, Clique-width, Tree-width, Courcelle’s theorem, FPT in P} }
Published in: LIPIcs, Volume 214, 16th International Symposium on Parameterized and Exact Computation (IPEC 2021)
Guillaume Ducoffe. Optimal Centrality Computations Within Bounded Clique-Width Graphs. In 16th International Symposium on Parameterized and Exact Computation (IPEC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 214, pp. 16:1-16:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ducoffe:LIPIcs.IPEC.2021.16, author = {Ducoffe, Guillaume}, title = {{Optimal Centrality Computations Within Bounded Clique-Width Graphs}}, booktitle = {16th International Symposium on Parameterized and Exact Computation (IPEC 2021)}, pages = {16:1--16:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-216-7}, ISSN = {1868-8969}, year = {2021}, volume = {214}, editor = {Golovach, Petr A. and Zehavi, Meirav}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2021.16}, URN = {urn:nbn:de:0030-drops-153995}, doi = {10.4230/LIPIcs.IPEC.2021.16}, annote = {Keywords: Clique-width, Centralities computation, Facility Location problems, Distance-labeling scheme, Fine-grained complexity in P, Graph theory} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Guillaume Ducoffe. Isometric Embeddings in Trees and Their Use in Distance Problems. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 43:1-43:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ducoffe:LIPIcs.MFCS.2021.43, author = {Ducoffe, Guillaume}, title = {{Isometric Embeddings in Trees and Their Use in Distance Problems}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {43:1--43:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.43}, URN = {urn:nbn:de:0030-drops-144835}, doi = {10.4230/LIPIcs.MFCS.2021.43}, annote = {Keywords: Tree embeddings, Range queries, Centroid decomposition, Heavy-path decomposition, Diameter, Radius and all Eccentricities computations} }
Published in: LIPIcs, Volume 202, 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)
Guillaume Ducoffe. On Computing the Average Distance for Some Chordal-Like Graphs. In 46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 202, pp. 44:1-44:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{ducoffe:LIPIcs.MFCS.2021.44, author = {Ducoffe, Guillaume}, title = {{On Computing the Average Distance for Some Chordal-Like Graphs}}, booktitle = {46th International Symposium on Mathematical Foundations of Computer Science (MFCS 2021)}, pages = {44:1--44:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-201-3}, ISSN = {1868-8969}, year = {2021}, volume = {202}, editor = {Bonchi, Filippo and Puglisi, Simon J.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2021.44}, URN = {urn:nbn:de:0030-drops-144841}, doi = {10.4230/LIPIcs.MFCS.2021.44}, annote = {Keywords: Wiener index, Graph diameter, Hardness in P, Chordal graphs, Helly graphs} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Guillaume Ducoffe. Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 49:1-49:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ducoffe:LIPIcs.ICALP.2019.49, author = {Ducoffe, Guillaume}, title = {{Faster Approximation Algorithms for Computing Shortest Cycles on Weighted Graphs}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {49:1--49:13}, 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.49}, URN = {urn:nbn:de:0030-drops-106254}, doi = {10.4230/LIPIcs.ICALP.2019.49}, annote = {Keywords: girth, weighted graphs, approximation algorithms} }
Published in: OASIcs, Volume 69, 2nd Symposium on Simplicity in Algorithms (SOSA 2019)
Guillaume Ducoffe. A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters. In 2nd Symposium on Simplicity in Algorithms (SOSA 2019). Open Access Series in Informatics (OASIcs), Volume 69, pp. 12:1-12:7, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{ducoffe:OASIcs.SOSA.2019.12, author = {Ducoffe, Guillaume}, title = {{A New Application of Orthogonal Range Searching for Computing Giant Graph Diameters}}, booktitle = {2nd Symposium on Simplicity in Algorithms (SOSA 2019)}, pages = {12:1--12:7}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-95977-099-6}, ISSN = {2190-6807}, year = {2019}, volume = {69}, editor = {Fineman, Jeremy T. and Mitzenmacher, Michael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.SOSA.2019.12}, URN = {urn:nbn:de:0030-drops-100383}, doi = {10.4230/OASIcs.SOSA.2019.12}, annote = {Keywords: Graph diameter, Orthogonal Range Queries, Hardness in P, FPT in P} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Guillaume Ducoffe and Alexandru Popa. The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ducoffe_et_al:LIPIcs.ISAAC.2018.6, author = {Ducoffe, Guillaume and Popa, Alexandru}, title = {{The Use of a Pruned Modular Decomposition for Maximum Matching Algorithms on Some Graph Classes}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {6:1--6:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.6}, URN = {urn:nbn:de:0030-drops-99549}, doi = {10.4230/LIPIcs.ISAAC.2018.6}, annote = {Keywords: maximum matching, FPT in P, modular decomposition, pruned graphs, one-vertex extensions, P\underline4-structure} }
Published in: LIPIcs, Volume 123, 29th International Symposium on Algorithms and Computation (ISAAC 2018)
Guillaume Ducoffe and Alexandru Popa. The b-Matching Problem in Distance-Hereditary Graphs and Beyond. In 29th International Symposium on Algorithms and Computation (ISAAC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 123, pp. 30:1-30:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{ducoffe_et_al:LIPIcs.ISAAC.2018.30, author = {Ducoffe, Guillaume and Popa, Alexandru}, title = {{The b-Matching Problem in Distance-Hereditary Graphs and Beyond}}, booktitle = {29th International Symposium on Algorithms and Computation (ISAAC 2018)}, pages = {30:1--30:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-094-1}, ISSN = {1868-8969}, year = {2018}, volume = {123}, editor = {Hsu, Wen-Lian and Lee, Der-Tsai and Liao, Chung-Shou}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2018.30}, URN = {urn:nbn:de:0030-drops-99783}, doi = {10.4230/LIPIcs.ISAAC.2018.30}, annote = {Keywords: maximum-cardinality matching, b-matching, FPT in P, split decomposition, distance-hereditary graphs} }
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 100, 9th International Conference on Fun with Algorithms (FUN 2018)
Jean-Claude Bermond, Augustin Chaintreau, Guillaume Ducoffe, and Dorian Mazauric. How long does it take for all users in a social network to choose their communities?. In 9th International Conference on Fun with Algorithms (FUN 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 100, pp. 6:1-6:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bermond_et_al:LIPIcs.FUN.2018.6, author = {Bermond, Jean-Claude and Chaintreau, Augustin and Ducoffe, Guillaume and Mazauric, Dorian}, title = {{How long does it take for all users in a social network to choose their communities?}}, booktitle = {9th International Conference on Fun with Algorithms (FUN 2018)}, pages = {6:1--6:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-067-5}, ISSN = {1868-8969}, year = {2018}, volume = {100}, editor = {Ito, Hiro and Leonardi, Stefano and Pagli, Linda and Prencipe, Giuseppe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2018.6}, URN = {urn:nbn:de:0030-drops-87972}, doi = {10.4230/LIPIcs.FUN.2018.6}, annote = {Keywords: communities, social networks, integer partitions, coloring games, graphs} }
Feedback for Dagstuhl Publishing