Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
Jingbang Chen, Meng He, J. Ian Munro, Richard Peng, Kaiyu Wu, and Daniel J. Zhang. Distance Queries over Dynamic Interval Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 18:1-18:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{chen_et_al:LIPIcs.ISAAC.2023.18, author = {Chen, Jingbang and He, Meng and Munro, J. Ian and Peng, Richard and Wu, Kaiyu and Zhang, Daniel J.}, title = {{Distance Queries over Dynamic Interval Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {18:1--18:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.18}, URN = {urn:nbn:de:0030-drops-193207}, doi = {10.4230/LIPIcs.ISAAC.2023.18}, annote = {Keywords: interval graph, proper interval graph, intersection graph, geometric intersection graph, distance oracle, distance query, shortest path query, dynamic graph} }
Published in: LIPIcs, Volume 274, 31st Annual European Symposium on Algorithms (ESA 2023)
Goran Zuzic. A Simple Boosting Framework for Transshipment. In 31st Annual European Symposium on Algorithms (ESA 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 274, pp. 104:1-104:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{zuzic:LIPIcs.ESA.2023.104, author = {Zuzic, Goran}, title = {{A Simple Boosting Framework for Transshipment}}, booktitle = {31st Annual European Symposium on Algorithms (ESA 2023)}, pages = {104:1--104:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-295-2}, ISSN = {1868-8969}, year = {2023}, volume = {274}, editor = {G{\o}rtz, Inge Li and Farach-Colton, Martin and Puglisi, Simon J. 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.2023.104}, URN = {urn:nbn:de:0030-drops-187570}, doi = {10.4230/LIPIcs.ESA.2023.104}, annote = {Keywords: mixed continuous-discrete optimization, boosting, multiplicative weights, theoretical computer science, shortest path, parallel algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Rasmus Kyng. An Almost-Linear Time Algorithm for Maximum Flow and More (Invited Talk). In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, p. 2:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{kyng:LIPIcs.ICALP.2023.2, author = {Kyng, Rasmus}, title = {{An Almost-Linear Time Algorithm for Maximum Flow and More}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {2:1--2:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.2}, URN = {urn:nbn:de:0030-drops-180543}, doi = {10.4230/LIPIcs.ICALP.2023.2}, annote = {Keywords: Maximum flow, Minimum cost flow, Data structures, Interior point methods, Convex optimization} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
Gramoz Goranci and Monika Henzinger. Efficient Data Structures for Incremental Exact and Approximate Maximum Flow. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 69:1-69:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{goranci_et_al:LIPIcs.ICALP.2023.69, author = {Goranci, Gramoz and Henzinger, Monika}, title = {{Efficient Data Structures for Incremental Exact and Approximate Maximum Flow}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {69:1--69:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.69}, URN = {urn:nbn:de:0030-drops-181212}, doi = {10.4230/LIPIcs.ICALP.2023.69}, annote = {Keywords: dynamic graph algorithms, maximum flow, data structures} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Monika Henzinger, Billy Jin, Richard Peng, and David P. Williamson. A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 69:1-69:22, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{henzinger_et_al:LIPIcs.ITCS.2023.69, author = {Henzinger, Monika and Jin, Billy and Peng, Richard and Williamson, David P.}, title = {{A Combinatorial Cut-Toggling Algorithm for Solving Laplacian Linear Systems}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {69:1--69:22}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.69}, URN = {urn:nbn:de:0030-drops-175720}, doi = {10.4230/LIPIcs.ITCS.2023.69}, annote = {Keywords: Laplacian solver, electrical flow, data structure} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Yang P. Liu. Vertex Sparsification for Edge Connectivity in Polynomial Time. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 83:1-83:15, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{liu:LIPIcs.ITCS.2023.83, author = {Liu, Yang P.}, title = {{Vertex Sparsification for Edge Connectivity in Polynomial Time}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {83:1--83:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-263-1}, ISSN = {1868-8969}, year = {2023}, volume = {251}, editor = {Tauman Kalai, Yael}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.83}, URN = {urn:nbn:de:0030-drops-175863}, doi = {10.4230/LIPIcs.ITCS.2023.83}, annote = {Keywords: Vertex-sparsification, edge-connectivity, Gammoids} }
Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)
Han Jiang, Shang-En Huang, Thatchaphol Saranurak, and Tian Zhang. Vertex Sparsifiers for Hyperedge Connectivity. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 70:1-70:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{jiang_et_al:LIPIcs.ESA.2022.70, author = {Jiang, Han and Huang, Shang-En and Saranurak, Thatchaphol and Zhang, Tian}, title = {{Vertex Sparsifiers for Hyperedge Connectivity}}, booktitle = {30th Annual European Symposium on Algorithms (ESA 2022)}, pages = {70:1--70:13}, 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.70}, URN = {urn:nbn:de:0030-drops-170081}, doi = {10.4230/LIPIcs.ESA.2022.70}, annote = {Keywords: Vertex sparsifier, hypergraph, connectivity} }
Published in: LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)
Sepehr Assadi, Aaron Bernstein, and Aditi Dudeja. Decremental Matching in General Graphs. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 229, pp. 11:1-11:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{assadi_et_al:LIPIcs.ICALP.2022.11, author = {Assadi, Sepehr and Bernstein, Aaron and Dudeja, Aditi}, title = {{Decremental Matching in General Graphs}}, booktitle = {49th International Colloquium on Automata, Languages, and Programming (ICALP 2022)}, pages = {11:1--11:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-235-8}, ISSN = {1868-8969}, year = {2022}, volume = {229}, editor = {Boja\'{n}czyk, Miko{\l}aj and Merelli, Emanuela and Woodruff, David P.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.11}, URN = {urn:nbn:de:0030-drops-163528}, doi = {10.4230/LIPIcs.ICALP.2022.11}, annote = {Keywords: Dynamic algorithms, matching, primal-dual algorithms} }
Published in: LIPIcs, Volume 215, 13th Innovations in Theoretical Computer Science Conference (ITCS 2022)
Sílvia Casacuberta and Rasmus Kyng. Faster Sparse Matrix Inversion and Rank Computation in Finite Fields. In 13th Innovations in Theoretical Computer Science Conference (ITCS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 215, pp. 33:1-33:24, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{casacuberta_et_al:LIPIcs.ITCS.2022.33, author = {Casacuberta, S{\'\i}lvia and Kyng, Rasmus}, title = {{Faster Sparse Matrix Inversion and Rank Computation in Finite Fields}}, booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)}, pages = {33:1--33:24}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-217-4}, ISSN = {1868-8969}, year = {2022}, volume = {215}, editor = {Braverman, Mark}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2022.33}, URN = {urn:nbn:de:0030-drops-156290}, doi = {10.4230/LIPIcs.ITCS.2022.33}, annote = {Keywords: Matrix inversion, rank computation, displacement operators, numerical linear algebra} }
Published in: LIPIcs, Volume 182, 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)
Yin Tat Lee. Convex Optimization and Dynamic Data Structure (Invited Talk). In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 182, p. 3:1, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{lee:LIPIcs.FSTTCS.2020.3, author = {Lee, Yin Tat}, title = {{Convex Optimization and Dynamic Data Structure}}, booktitle = {40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020)}, pages = {3:1--3:1}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-174-0}, ISSN = {1868-8969}, year = {2020}, volume = {182}, editor = {Saxena, Nitin and Simon, Sunil}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2020.3}, URN = {urn:nbn:de:0030-drops-132440}, doi = {10.4230/LIPIcs.FSTTCS.2020.3}, annote = {Keywords: Convex Optimization, Dynamic Data Structure} }
Published in: Dagstuhl Reports, Volume 8, Issue 6 (2019)
Henning Meyerhenke, Richard Peng, and Ilya Safro. High-Performance Graph Algorithms (Dagstuhl Seminar 18241). In Dagstuhl Reports, Volume 8, Issue 6, pp. 19-39, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@Article{meyerhenke_et_al:DagRep.8.6.19, author = {Meyerhenke, Henning and Peng, Richard and Safro, Ilya}, title = {{High-Performance Graph Algorithms (Dagstuhl Seminar 18241)}}, pages = {19--39}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2018}, volume = {8}, number = {6}, editor = {Meyerhenke, Henning and Peng, Richard and Safro, Ilya}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.8.6.19}, URN = {urn:nbn:de:0030-drops-100475}, doi = {10.4230/DagRep.8.6.19}, annote = {Keywords: algorithm engineering, combinatorial scientific computing, graph algorithms, high-performance computing, theoretical computer science} }
Published in: LIPIcs, Volume 81, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)
Gorav Jindal, Pavel Kolev, Richard Peng, and Saurabh Sawlani. Density Independent Algorithms for Sparsifying k-Step Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 81, pp. 14:1-14:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@InProceedings{jindal_et_al:LIPIcs.APPROX-RANDOM.2017.14, author = {Jindal, Gorav and Kolev, Pavel and Peng, Richard and Sawlani, Saurabh}, title = {{Density Independent Algorithms for Sparsifying k-Step Random Walks}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017)}, pages = {14:1--14:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-044-6}, ISSN = {1868-8969}, year = {2017}, volume = {81}, editor = {Jansen, Klaus and Rolim, Jos\'{e} D. P. and Williamson, David P. and Vempala, Santosh S.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2017.14}, URN = {urn:nbn:de:0030-drops-75638}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2017.14}, annote = {Keywords: random walks, graph sparsification, spectral graph theory, effective resistances} }
Published in: LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1
Florian Kluge. Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results. In LITES, Volume 4, Issue 1 (2017). Leibniz Transactions on Embedded Systems, Volume 4, Issue 1, pp. 02:1-02:25, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)
@Article{kluge:LITES-v004-i001-a002, author = {Kluge, Florian}, title = {{Utility-Based Scheduling of (m,k)-firm Real-Time Tasks - New Empirical Results}}, booktitle = {LITES, Volume 4, Issue 1 (2017)}, pages = {02:1--02:25}, journal = {Leibniz Transactions on Embedded Systems}, ISSN = {2199-2002}, year = {2017}, volume = {4}, number = {1}, editor = {Kluge, Florian}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LITES-v004-i001-a002}, doi = {10.4230/LITES-v004-i001-a002}, annote = {Keywords: Real-time Scheduling, (m, k)-Firm Real-Time Tasks} }
Published in: LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2
Thomas Carle, Dumitru Potop-Butucaru, Yves Sorel, and David Lesens. From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation. In LITES, Volume 2, Issue 2 (2015). Leibniz Transactions on Embedded Systems, Volume 2, Issue 2, pp. 01:1-01:30, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015)
@Article{carle_et_al:LITES-v002-i002-a001, author = {Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David}, title = {{From Dataflow Specification to Multiprocessor Partitioned Time-triggered Real-time Implementation}}, booktitle = {LITES, Volume 2, Issue 2 (2015)}, pages = {01:1--01:30}, journal = {Leibniz Transactions on Embedded Systems}, ISSN = {2199-2002}, year = {2015}, volume = {2}, number = {2}, editor = {Carle, Thomas and Potop-Butucaru, Dumitru and Sorel, Yves and Lesens, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LITES-v002-i002-a001}, doi = {10.4230/LITES-v002-i002-a001}, annote = {Keywords: Time-triggered, Off-line real-time scheduling, Temporal partitioning} }
Published in: LIPIcs, Volume 14, 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)
Ioannis Koutis, Alex Levin, and Richard Peng. Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices. In 29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012). Leibniz International Proceedings in Informatics (LIPIcs), Volume 14, pp. 266-277, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2012)
@InProceedings{koutis_et_al:LIPIcs.STACS.2012.266, author = {Koutis, Ioannis and Levin, Alex and Peng, Richard}, title = {{Improved Spectral Sparsification and Numerical Algorithms for SDD Matrices}}, booktitle = {29th International Symposium on Theoretical Aspects of Computer Science (STACS 2012)}, pages = {266--277}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-35-4}, ISSN = {1868-8969}, year = {2012}, volume = {14}, editor = {D\"{u}rr, Christoph and Wilke, Thomas}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2012.266}, URN = {urn:nbn:de:0030-drops-34348}, doi = {10.4230/LIPIcs.STACS.2012.266}, annote = {Keywords: Spectral sparsification, linear system solving} }
Feedback for Dagstuhl Publishing