Published in: LIPIcs, Volume 322, 35th International Symposium on Algorithms and Computation (ISAAC 2024)
Prosenjit Bose, Darryl Hill, Michiel Smid, and Tyler Tuttle. On the Spanning and Routing Ratios of the Yao-Four Graph. In 35th International Symposium on Algorithms and Computation (ISAAC 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 322, pp. 15:1-15:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bose_et_al:LIPIcs.ISAAC.2024.15, author = {Bose, Prosenjit and Hill, Darryl and Smid, Michiel and Tuttle, Tyler}, title = {{On the Spanning and Routing Ratios of the Yao-Four Graph}}, booktitle = {35th International Symposium on Algorithms and Computation (ISAAC 2024)}, pages = {15:1--15:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-354-6}, ISSN = {1868-8969}, year = {2024}, volume = {322}, editor = {Mestre, Juli\'{a}n and Wirth, Anthony}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2024.15}, URN = {urn:nbn:de:0030-drops-221422}, doi = {10.4230/LIPIcs.ISAAC.2024.15}, annote = {Keywords: Yao graph, online routing, geometric spanners} }
Published in: LIPIcs, Volume 320, 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)
Greg Aloupis, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba D. Tóth, and Pavel Valtr. Noncrossing Longest Paths and Cycles. In 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 320, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{aloupis_et_al:LIPIcs.GD.2024.36, author = {Aloupis, Greg and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Eppstein, David and Maheshwari, Anil and Odak, Saeed and Smid, Michiel and T\'{o}th, Csaba D. and Valtr, Pavel}, title = {{Noncrossing Longest Paths and Cycles}}, booktitle = {32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)}, pages = {36:1--36:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-343-0}, ISSN = {1868-8969}, year = {2024}, volume = {320}, editor = {Felsner, Stefan and Klein, Karsten}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.GD.2024.36}, URN = {urn:nbn:de:0030-drops-213203}, doi = {10.4230/LIPIcs.GD.2024.36}, annote = {Keywords: Longest Paths, Longest Cycles, Noncrossing Paths, Noncrossing Cycles} }
Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)
Sayan Bandyapadhyay, Anil Maheshwari, Sasanka Roy, Michiel Smid, and Kasturi Varadarajan. Geometric Covering via Extraction Theorem. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 7:1-7:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bandyapadhyay_et_al:LIPIcs.ITCS.2024.7, author = {Bandyapadhyay, Sayan and Maheshwari, Anil and Roy, Sasanka and Smid, Michiel and Varadarajan, Kasturi}, title = {{Geometric Covering via Extraction Theorem}}, booktitle = {15th Innovations in Theoretical Computer Science Conference (ITCS 2024)}, pages = {7:1--7:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-309-6}, ISSN = {1868-8969}, year = {2024}, volume = {287}, editor = {Guruswami, Venkatesan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.7}, URN = {urn:nbn:de:0030-drops-195355}, doi = {10.4230/LIPIcs.ITCS.2024.7}, annote = {Keywords: Covering, Extraction theorem, Double-disks, Submodularity, Local search} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Sayan Bandyapadhyay, Anil Maheshwari, and Michiel Smid. Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bandyapadhyay_et_al:LIPIcs.ISAAC.2021.44, author = {Bandyapadhyay, Sayan and Maheshwari, Anil and Smid, Michiel}, title = {{Exact and Approximation Algorithms for Many-To-Many Point Matching in the Plane}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.44}, URN = {urn:nbn:de:0030-drops-154779}, doi = {10.4230/LIPIcs.ISAAC.2021.44}, annote = {Keywords: Many-to-many matching, bipartite, planar, geometric, approximation} }
Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)
Joyce Bacic, Saeed Mehrabi, and Michiel Smid. Shortest Beer Path Queries in Outerplanar Graphs. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 62:1-62:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@InProceedings{bacic_et_al:LIPIcs.ISAAC.2021.62, author = {Bacic, Joyce and Mehrabi, Saeed and Smid, Michiel}, title = {{Shortest Beer Path Queries in Outerplanar Graphs}}, booktitle = {32nd International Symposium on Algorithms and Computation (ISAAC 2021)}, pages = {62:1--62:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-214-3}, ISSN = {1868-8969}, year = {2021}, volume = {212}, editor = {Ahn, Hee-Kap and Sadakane, Kunihiko}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.62}, URN = {urn:nbn:de:0030-drops-154950}, doi = {10.4230/LIPIcs.ISAAC.2021.62}, annote = {Keywords: shortest paths, outerplanar graph} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Nicolas Bonichon, Prosenjit Bose, Jean-Lou De Carufel, Vincent Despré, Darryl Hill, and Michiel Smid. Improved Routing on the Delaunay Triangulation. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 22:1-22:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{bonichon_et_al:LIPIcs.ESA.2018.22, author = {Bonichon, Nicolas and Bose, Prosenjit and De Carufel, Jean-Lou and Despr\'{e}, Vincent and Hill, Darryl and Smid, Michiel}, title = {{Improved Routing on the Delaunay Triangulation}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {22:1--22:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-081-1}, ISSN = {1868-8969}, year = {2018}, volume = {112}, editor = {Azar, Yossi and Bast, Hannah and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2018.22}, URN = {urn:nbn:de:0030-drops-94857}, doi = {10.4230/LIPIcs.ESA.2018.22}, annote = {Keywords: Delaunay, local routing, geometric, graph} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
A. Karim Abu-Affash, Paz Carmi, Anil Maheshwari, Pat Morin, Michiel Smid, and Shakhar Smorodinsky. Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 2:1-2:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{abuaffash_et_al:LIPIcs.SoCG.2018.2, author = {Abu-Affash, A. Karim and Carmi, Paz and Maheshwari, Anil and Morin, Pat and Smid, Michiel and Smorodinsky, Shakhar}, title = {{Approximating Maximum Diameter-Bounded Subgraph in Unit Disk Graphs}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {2:1--2:12}, 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.2}, URN = {urn:nbn:de:0030-drops-87152}, doi = {10.4230/LIPIcs.SoCG.2018.2}, annote = {Keywords: Approximation algorithms, maximum diameter-bounded subgraph, unit disk graphs, fractional Helly theorem, VC-dimension} }
Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)
Ahmad Biniaz, Prosenjit Bose, Paz Carmi, Anil Maheshwari, Ian Munro, and Michiel Smid. Faster Algorithms for some Optimization Problems on Collinear Points. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 8:1-8:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{biniaz_et_al:LIPIcs.SoCG.2018.8, author = {Biniaz, Ahmad and Bose, Prosenjit and Carmi, Paz and Maheshwari, Anil and Munro, Ian and Smid, Michiel}, title = {{Faster Algorithms for some Optimization Problems on Collinear Points}}, booktitle = {34th International Symposium on Computational Geometry (SoCG 2018)}, pages = {8:1--8:14}, 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.8}, URN = {urn:nbn:de:0030-drops-87219}, doi = {10.4230/LIPIcs.SoCG.2018.8}, annote = {Keywords: collinear points, range assignment} }
Published in: LIPIcs, Volume 101, 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)
Ahmad Biniaz, Anil Maheshwari, and Michiel Smid. Flip Distance to some Plane Configurations. In 16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 101, pp. 11:1-11:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{biniaz_et_al:LIPIcs.SWAT.2018.11, author = {Biniaz, Ahmad and Maheshwari, Anil and Smid, Michiel}, title = {{Flip Distance to some Plane Configurations}}, booktitle = {16th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2018)}, pages = {11:1--11:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-068-2}, ISSN = {1868-8969}, year = {2018}, volume = {101}, editor = {Eppstein, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2018.11}, URN = {urn:nbn:de:0030-drops-88371}, doi = {10.4230/LIPIcs.SWAT.2018.11}, annote = {Keywords: flip distance, non-crossing edges, perfect matchings, spanning trees} }
Published in: LIPIcs, Volume 64, 27th International Symposium on Algorithms and Computation (ISAAC 2016)
Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Cyril Gavoille, Anil Maheshwari, and Michiel Smid. Towards Plane Spanners of Degree 3. In 27th International Symposium on Algorithms and Computation (ISAAC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 64, pp. 19:1-19:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{biniaz_et_al:LIPIcs.ISAAC.2016.19, author = {Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Gavoille, Cyril and Maheshwari, Anil and Smid, Michiel}, title = {{Towards Plane Spanners of Degree 3}}, booktitle = {27th International Symposium on Algorithms and Computation (ISAAC 2016)}, pages = {19:1--19:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-026-2}, ISSN = {1868-8969}, year = {2016}, volume = {64}, editor = {Hong, Seok-Hee}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2016.19}, URN = {urn:nbn:de:0030-drops-67887}, doi = {10.4230/LIPIcs.ISAAC.2016.19}, annote = {Keywords: plane spanners, degree-3 spanners, convex position, non-uniform lattice} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Mahdi Amani, Ahmad Biniaz, Prosenjit Bose, Jean-Lou De Carufel, Anil Maheshwari, and Michiel Smid. A Plane 1.88-Spanner for Points in Convex Position. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 25:1-25:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{amani_et_al:LIPIcs.SWAT.2016.25, author = {Amani, Mahdi and Biniaz, Ahmad and Bose, Prosenjit and De Carufel, Jean-Lou and Maheshwari, Anil and Smid, Michiel}, title = {{A Plane 1.88-Spanner for Points in Convex Position}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {25:1--25:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.25}, URN = {urn:nbn:de:0030-drops-60474}, doi = {10.4230/LIPIcs.SWAT.2016.25}, annote = {Keywords: points in convex position, plane spanner} }
Published in: LIPIcs, Volume 53, 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)
Jean-Lou De Carufel, Carsten Grimm, Anil Maheshwari, and Michiel Smid. Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts. In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 53, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@InProceedings{decarufel_et_al:LIPIcs.SWAT.2016.27, author = {De Carufel, Jean-Lou and Grimm, Carsten and Maheshwari, Anil and Smid, Michiel}, title = {{Minimizing the Continuous Diameter when Augmenting Paths and Cycles with Shortcuts}}, booktitle = {15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2016)}, pages = {27:1--27:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-011-8}, ISSN = {1868-8969}, year = {2016}, volume = {53}, editor = {Pagh, Rasmus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2016.27}, URN = {urn:nbn:de:0030-drops-60492}, doi = {10.4230/LIPIcs.SWAT.2016.27}, annote = {Keywords: Network Augmentation, Shortcuts, Diameter, Paths, Cycles} }
Published in: Dagstuhl Seminar Proceedings, Volume 9451, Geometric Networks, Metric Space Embeddings and Spatial Data Mining (2010)
Gautam Das, Joachim Gudmundsson, Rolf Klein, Christian Knauer, and Michiel Smid. 09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining. In Geometric Networks, Metric Space Embeddings and Spatial Data Mining. Dagstuhl Seminar Proceedings, Volume 9451, pp. 1-15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{das_et_al:DagSemProc.09451.1, author = {Das, Gautam and Gudmundsson, Joachim and Klein, Rolf and Knauer, Christian and Smid, Michiel}, title = {{09451 Abstracts Collection – Geometric Networks, Metric Space Embeddings and Spatial Data Mining}}, booktitle = {Geometric Networks, Metric Space Embeddings and Spatial Data Mining}, pages = {1--15}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {9451}, editor = {Gautam Das and Joachim Gudmundsson and Rolf Klein and Christian Knauer and Michiel Smid}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.09451.1}, URN = {urn:nbn:de:0030-drops-24380}, doi = {10.4230/DagSemProc.09451.1}, annote = {Keywords: Geometric networks, metric space embeddings, spatial data mining, spanners, dilation, distortion} }
Published in: Dagstuhl Seminar Proceedings, Volume 6481, Geometric Networks and Metric Space Embeddings (2007)
Joachim Gudmundsson, Rolf Klein, Giri Narasimhan, Michiel Smid, and Alexander Wolff. 06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings. In Geometric Networks and Metric Space Embeddings. Dagstuhl Seminar Proceedings, Volume 6481, pp. 1-21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2007)
@InProceedings{gudmundsson_et_al:DagSemProc.06481.1, author = {Gudmundsson, Joachim and Klein, Rolf and Narasimhan, Giri and Smid, Michiel and Wolff, Alexander}, title = {{06481 Abstracts Collection – Geometric Networks and Metric Space Embeddings}}, booktitle = {Geometric Networks and Metric Space Embeddings}, pages = {1--21}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2007}, volume = {6481}, editor = {Joachim Gudmundsson and Rolf Klein and Giri Narasimhan and Michiel Smid and Alexander Wolff}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagSemProc.06481.1}, URN = {urn:nbn:de:0030-drops-10291}, doi = {10.4230/DagSemProc.06481.1}, annote = {Keywords: Geometric networks, metric space embeddings, phylogenetic networks, spanners, dilation, distortion} }
Feedback for Dagstuhl Publishing