Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Manuel Cáceres, Brendan Mumey, Santeri Toivonen, and Alexandru I. Tomescu. Practical Minimum Path Cover. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{caceres_et_al:LIPIcs.SEA.2024.3, author = {C\'{a}ceres, Manuel and Mumey, Brendan and Toivonen, Santeri and Tomescu, Alexandru I.}, title = {{Practical Minimum Path Cover}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {3:1--3:19}, 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.3}, URN = {urn:nbn:de:0030-drops-203687}, doi = {10.4230/LIPIcs.SEA.2024.3}, annote = {Keywords: minimum path cover, directed acyclic graph, maximum flow, parameterized algorithms, edge sparsification, algorithm engineering} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Giovanna Kobus Conrado, Amir Kafshdar Goharshady, Pavel Hudec, Pingjiang Li, and Harshit Jitendra Motwani. Faster Treewidth-Based Approximations for Wiener Index. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 6:1-6:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{conrado_et_al:LIPIcs.SEA.2024.6, author = {Conrado, Giovanna Kobus and Goharshady, Amir Kafshdar and Hudec, Pavel and Li, Pingjiang and Motwani, Harshit Jitendra}, title = {{Faster Treewidth-Based Approximations for Wiener Index}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {6:1--6:19}, 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.6}, URN = {urn:nbn:de:0030-drops-203718}, doi = {10.4230/LIPIcs.SEA.2024.6}, annote = {Keywords: Computational Chemistry, Treewidth, Wiener Index} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Daniel Hambly, Rhyd Lewis, and Padraig Corcoran. Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 15:1-15:11, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{hambly_et_al:LIPIcs.SEA.2024.15, author = {Hambly, Daniel and Lewis, Rhyd and Corcoran, Padraig}, title = {{Determining Fixed-Length Paths in Directed and Undirected Edge-Weighted Graphs}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {15:1--15:11}, 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.15}, URN = {urn:nbn:de:0030-drops-203805}, doi = {10.4230/LIPIcs.SEA.2024.15}, annote = {Keywords: Graphs, paths, backtracking, integer programming, Yen’s algorithm} }
Published in: LIPIcs, Volume 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Kenneth Langedal, Demian Hespe, and Peter Sanders. Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 20:1-20:21, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{langedal_et_al:LIPIcs.SEA.2024.20, author = {Langedal, Kenneth and Hespe, Demian and Sanders, Peter}, title = {{Targeted Branching for the Maximum Independent Set Problem Using Graph Neural Networks}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {20:1--20:21}, 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.20}, URN = {urn:nbn:de:0030-drops-203853}, doi = {10.4230/LIPIcs.SEA.2024.20}, annote = {Keywords: Graphs, Independent Set, Vertex Cover, Graph Neural Networks, Branch-and-Reduce} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Li Chen and Mingquan Ye. High-Accuracy Multicommodity Flows via Iterative Refinement. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 45:1-45:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chen_et_al:LIPIcs.ICALP.2024.45, author = {Chen, Li and Ye, Mingquan}, title = {{High-Accuracy Multicommodity Flows via Iterative Refinement}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {45:1--45:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.45}, URN = {urn:nbn:de:0030-drops-201887}, doi = {10.4230/LIPIcs.ICALP.2024.45}, annote = {Keywords: High-accuracy multicommodity flow, Iterative refinement framework, Convex flow solver} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Holger Dell, John Lapinskas, and Kitty Meeks. Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 54:1-54:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dell_et_al:LIPIcs.ICALP.2024.54, author = {Dell, Holger and Lapinskas, John and Meeks, Kitty}, title = {{Nearly Optimal Independence Oracle Algorithms for Edge Estimation in Hypergraphs}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {54:1--54:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.54}, URN = {urn:nbn:de:0030-drops-201977}, doi = {10.4230/LIPIcs.ICALP.2024.54}, annote = {Keywords: Graph oracles, Fine-grained complexity, Approximate counting, Hypergraphs} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Greg Bodwin, Chengyuan Deng, Jie Gao, Gary Hoppenworth, Jalaj Upadhyay, and Chen Wang. The Discrepancy of Shortest Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 27:1-27:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{bodwin_et_al:LIPIcs.ICALP.2024.27, author = {Bodwin, Greg and Deng, Chengyuan and Gao, Jie and Hoppenworth, Gary and Upadhyay, Jalaj and Wang, Chen}, title = {{The Discrepancy of Shortest Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {27:1--27:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.27}, URN = {urn:nbn:de:0030-drops-201705}, doi = {10.4230/LIPIcs.ICALP.2024.27}, annote = {Keywords: Discrepancy, hereditary discrepancy, shortest paths, differential privacy} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Ce Jin, Michael Kapralov, Sepideh Mahabadi, and Ali Vakilian. Streaming Algorithms for Connectivity Augmentation. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 93:1-93:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{jin_et_al:LIPIcs.ICALP.2024.93, author = {Jin, Ce and Kapralov, Michael and Mahabadi, Sepideh and Vakilian, Ali}, title = {{Streaming Algorithms for Connectivity Augmentation}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {93:1--93:20}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.93}, URN = {urn:nbn:de:0030-drops-202367}, doi = {10.4230/LIPIcs.ICALP.2024.93}, annote = {Keywords: streaming algorithms, connectivity augmentation} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Tsvi Kopelowitz, Ariel Korin, and Liam Roditty. On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 101:1-101:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{kopelowitz_et_al:LIPIcs.ICALP.2024.101, author = {Kopelowitz, Tsvi and Korin, Ariel and Roditty, Liam}, title = {{On the Space Usage of Approximate Distance Oracles with Sub-2 Stretch}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {101:1--101:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.101}, URN = {urn:nbn:de:0030-drops-202443}, doi = {10.4230/LIPIcs.ICALP.2024.101}, annote = {Keywords: Graph algorithms, Approximate distance oracle, data structures, shortest path} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Bruno Loff and Mateusz Skomra. Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 147:1-147:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{loff_et_al:LIPIcs.ICALP.2024.147, author = {Loff, Bruno and Skomra, Mateusz}, title = {{Smoothed Analysis of Deterministic Discounted and Mean-Payoff Games}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {147:1--147:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-322-5}, ISSN = {1868-8969}, year = {2024}, volume = {297}, editor = {Bringmann, Karl and Grohe, Martin and Puppis, Gabriele and Svensson, Ola}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2024.147}, URN = {urn:nbn:de:0030-drops-202908}, doi = {10.4230/LIPIcs.ICALP.2024.147}, annote = {Keywords: Mean-payoff games, discounted games, policy iteration, smoothed analysis} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Yuanyuan Dong, Andrew V. Goldberg, Alexander Noe, Nikos Parotsidis, Mauricio G.C. Resende, and Quico Spaen. A Local Search Algorithm for Large Maximum Weight Independent Set Problems. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 45:1-45:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{dong_et_al:LIPIcs.ESA.2022.45, author = {Dong, Yuanyuan and Goldberg, Andrew V. and Noe, Alexander and Parotsidis, Nikos and Resende, Mauricio G.C. and Spaen, Quico}, title = {{A Local Search Algorithm for Large Maximum Weight Independent Set Problems}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {45:1--45:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-247-1}, ISSN = {1868-8969}, year = {2022}, volume = {244}, editor = {Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva 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.2022.45}, URN = {urn:nbn:de:0030-drops-169839}, doi = {10.4230/LIPIcs.ESA.2022.45}, annote = {Keywords: GRASP, local search, maximum-weight independent set, path-relinking, heuristic, metaheuristic} }
Published in: LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019)
Pankaj K. Agarwal, Hsien-Chih Chang, and Allen Xiao. Efficient Algorithms for Geometric Partial Matching. In 35th International Symposium on Computational Geometry (SoCG 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 129, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{agarwal_et_al:LIPIcs.SoCG.2019.6, author = {Agarwal, Pankaj K. and Chang, Hsien-Chih and Xiao, Allen}, title = {{Efficient Algorithms for Geometric Partial Matching}}, booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)}, pages = {6:1--6:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-104-7}, ISSN = {1868-8969}, year = {2019}, volume = {129}, editor = {Barequet, Gill and Wang, Yusu}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.6}, URN = {urn:nbn:de:0030-drops-104109}, doi = {10.4230/LIPIcs.SoCG.2019.6}, annote = {Keywords: partial matching, transportation, optimal transport, minimum-cost flow, bichromatic closest pair} }
Published in: LIPIcs, Volume 30, 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)
Andrew V. Goldberg, Haim Kaplan, Sagi Hed, and Robert E. Tarjan. Minimum Cost Flows in Graphs with Unit Capacities. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 406-419, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
@InProceedings{goldberg_et_al:LIPIcs.STACS.2015.406, author = {Goldberg, Andrew V. and Kaplan, Haim and Hed, Sagi and Tarjan, Robert E.}, title = {{Minimum Cost Flows in Graphs with Unit Capacities}}, booktitle = {32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015)}, pages = {406--419}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-78-1}, ISSN = {1868-8969}, year = {2015}, volume = {30}, editor = {Mayr, Ernst W. and Ollinger, Nicolas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2015.406}, URN = {urn:nbn:de:0030-drops-49304}, doi = {10.4230/LIPIcs.STACS.2015.406}, annote = {Keywords: minimum cost flow, bipartite matching, unit capacity, cost scaling} }
Published in: Dagstuhl Reports, Volume 3, Issue 9 (2014)
Andrew V. Goldberg, Giuseppe F. Italiano, David S. Johnson, and Dorothea Wagner. Algorithm Engineering (Dagstuhl Seminar 13391). In Dagstuhl Reports, Volume 3, Issue 9, pp. 169-189, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@Article{goldberg_et_al:DagRep.3.9.169, author = {Goldberg, Andrew V. and Italiano, Giuseppe F. and Johnson, David S. and Wagner, Dorothea}, title = {{Algorithm Engineering (Dagstuhl Seminar 13391)}}, pages = {169--189}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2014}, volume = {3}, number = {9}, editor = {Goldberg, Andrew V. and Italiano, Giuseppe F. and Johnson, David S. and Wagner, Dorothea}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.3.9.169}, URN = {urn:nbn:de:0030-drops-44214}, doi = {10.4230/DagRep.3.9.169}, annote = {Keywords: Algorithm Engineering, Science of Algorithmics, Manycore Algorithms, Certifying Algorithms, Web Search, Large Graphs} }
Published in: OASIcs, Volume 20, 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (2011)
Daniel Delling, Andrew V. Goldberg, and Renato F. Werneck. Faster Batched Shortest Paths in Road Networks. In 11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems. Open Access Series in Informatics (OASIcs), Volume 20, pp. 52-63, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)
@InProceedings{delling_et_al:OASIcs.ATMOS.2011.52, author = {Delling, Daniel and Goldberg, Andrew V. and Werneck, Renato F.}, title = {{Faster Batched Shortest Paths in Road Networks}}, booktitle = {11th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems}, pages = {52--63}, series = {Open Access Series in Informatics (OASIcs)}, ISBN = {978-3-939897-33-0}, ISSN = {2190-6807}, year = {2011}, volume = {20}, editor = {Caprara, Alberto and Kontogiannis, Spyros}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/OASIcs.ATMOS.2011.52}, URN = {urn:nbn:de:0030-drops-32663}, doi = {10.4230/OASIcs.ATMOS.2011.52}, annote = {Keywords: shortest paths, contraction hierarchies, many-to-many, one-to-many} }