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 301, 22nd International Symposium on Experimental Algorithms (SEA 2024)
Christoph Staudt, Mark Blacher, Julien Klaus, Farin Lippmann, and Joachim Giesen. Improved Cut Strategy for Tensor Network Contraction Orders. In 22nd International Symposium on Experimental Algorithms (SEA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 301, pp. 27:1-27:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{staudt_et_al:LIPIcs.SEA.2024.27, author = {Staudt, Christoph and Blacher, Mark and Klaus, Julien and Lippmann, Farin and Giesen, Joachim}, title = {{Improved Cut Strategy for Tensor Network Contraction Orders}}, booktitle = {22nd International Symposium on Experimental Algorithms (SEA 2024)}, pages = {27:1--27: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.27}, URN = {urn:nbn:de:0030-drops-203924}, doi = {10.4230/LIPIcs.SEA.2024.27}, annote = {Keywords: tensor network, contraction order, graph partitioniong, quantum simulation} }
Published in: LIPIcs, Volume 298, 36th Euromicro Conference on Real-Time Systems (ECRTS 2024)
Daniel Oliveira, Weifan Chen, Sandro Pinto, and Renato Mancuso. Shared Resource Contention in MCUs: A Reality Check and the Quest for Timeliness. In 36th Euromicro Conference on Real-Time Systems (ECRTS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 298, pp. 5:1-5:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{oliveira_et_al:LIPIcs.ECRTS.2024.5, author = {Oliveira, Daniel and Chen, Weifan and Pinto, Sandro and Mancuso, Renato}, title = {{Shared Resource Contention in MCUs: A Reality Check and the Quest for Timeliness}}, booktitle = {36th Euromicro Conference on Real-Time Systems (ECRTS 2024)}, pages = {5:1--5:25}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-324-9}, ISSN = {1868-8969}, year = {2024}, volume = {298}, editor = {Pellizzoni, Rodolfo}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECRTS.2024.5}, URN = {urn:nbn:de:0030-drops-203088}, doi = {10.4230/LIPIcs.ECRTS.2024.5}, annote = {Keywords: multi-core microcontrollers, shared resources contention, progress-aware regulation} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 37:1-37:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{censorhillel_et_al:LIPIcs.ICALP.2024.37, author = {Censor-Hillel, Keren and Even, Tomer and Vassilevska Williams, Virginia}, title = {{Fast Approximate Counting of Cycles}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {37:1--37: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.37}, URN = {urn:nbn:de:0030-drops-201809}, doi = {10.4230/LIPIcs.ICALP.2024.37}, annote = {Keywords: Approximate triangle counting, Approximate cycle counting Fast matrix multiplication, Fast rectangular matrix multiplication} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shiri Chechik and Tianyi Zhang. Faster Algorithms for Dual-Failure Replacement Paths. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 41:1-41:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{chechik_et_al:LIPIcs.ICALP.2024.41, author = {Chechik, Shiri and Zhang, Tianyi}, title = {{Faster Algorithms for Dual-Failure Replacement Paths}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {41:1--41: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.41}, URN = {urn:nbn:de:0030-drops-201849}, doi = {10.4230/LIPIcs.ICALP.2024.41}, annote = {Keywords: graph algorithms, shortest paths, replacement paths} }
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)
Nick Fischer and Leo Wennmann. Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 64:1-64:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{fischer_et_al:LIPIcs.ICALP.2024.64, author = {Fischer, Nick and Wennmann, Leo}, title = {{Minimizing Tardy Processing Time on a Single Machine in Near-Linear Time}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {64:1--64:15}, 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.64}, URN = {urn:nbn:de:0030-drops-202079}, doi = {10.4230/LIPIcs.ICALP.2024.64}, annote = {Keywords: Scheduling, Fine-Grained Complexity, Dynamic Strings} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Shi Li, Chenyang Xu, and Ruilong Zhang. Polylogarithmic Approximations for Robust s-t Path. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 106:1-106:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{li_et_al:LIPIcs.ICALP.2024.106, author = {Li, Shi and Xu, Chenyang and Zhang, Ruilong}, title = {{Polylogarithmic Approximations for Robust s-t Path}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {106:1--106: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.106}, URN = {urn:nbn:de:0030-drops-202497}, doi = {10.4230/LIPIcs.ICALP.2024.106}, annote = {Keywords: Approximation Algorithm, Randomized LP Rounding, Robust s-t Path} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Sariel Har-Peled, Elfarouk Harb, and Vasilis Livanos. Oracle-Augmented Prophet Inequalities. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 81:1-81:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{harpeled_et_al:LIPIcs.ICALP.2024.81, author = {Har-Peled, Sariel and Harb, Elfarouk and Livanos, Vasilis}, title = {{Oracle-Augmented Prophet Inequalities}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {81:1--81: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.81}, URN = {urn:nbn:de:0030-drops-202245}, doi = {10.4230/LIPIcs.ICALP.2024.81}, annote = {Keywords: prophet inequalities, predictions, top-1-of-k model} }
Published in: LIPIcs, Volume 297, 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)
Cheng Zhang, Arthur Azevedo de Amorim, and Marco Gaboardi. Domain Reasoning in TopKAT. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 157:1-157:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{zhang_et_al:LIPIcs.ICALP.2024.157, author = {Zhang, Cheng and de Amorim, Arthur Azevedo and Gaboardi, Marco}, title = {{Domain Reasoning in TopKAT}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {157:1--157: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.157}, URN = {urn:nbn:de:0030-drops-203003}, doi = {10.4230/LIPIcs.ICALP.2024.157}, annote = {Keywords: Kleene algebra, Kleene Algebra With Tests, Kleene Algebra With Domain, Kleene Algebra With Top and Tests, Completeness, Decidability} }
Published in: Dagstuhl Manifestos, Volume 10, Issue 1 (2024)
James P. Delgrande, Birte Glimm, Thomas Meyer, Miroslaw Truszczynski, and Frank Wolter. Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282). In Dagstuhl Manifestos, Volume 10, Issue 1, pp. 1-61, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{delgrande_et_al:DagMan.10.1.1, author = {Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank}, title = {{Current and Future Challenges in Knowledge Representation and Reasoning (Dagstuhl Perspectives Workshop 22282)}}, pages = {1--61}, journal = {Dagstuhl Manifestos}, ISSN = {2193-2433}, year = {2024}, volume = {10}, number = {1}, editor = {Delgrande, James P. and Glimm, Birte and Meyer, Thomas and Truszczynski, Miroslaw and Wolter, Frank}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagMan.10.1.1}, URN = {urn:nbn:de:0030-drops-201403}, doi = {10.4230/DagMan.10.1.1}, annote = {Keywords: Knowledge representation and reasoning, Applications of logics, Declarative representations, Formal logic} }
Published in: TGDK, Volume 2, Issue 1 (2024): Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge, Volume 2, Issue 1
Pieter Bonte, Jean-Paul Calbimonte, Daniel de Leng, Daniele Dell'Aglio, Emanuele Della Valle, Thomas Eiter, Federico Giannini, Fredrik Heintz, Konstantin Schekotihin, Danh Le-Phuoc, Alessandra Mileo, Patrik Schneider, Riccardo Tommasini, Jacopo Urbani, and Giacomo Ziffer. Grounding Stream Reasoning Research. In Special Issue on Trends in Graph Data and Knowledge - Part 2. Transactions on Graph Data and Knowledge (TGDK), Volume 2, Issue 1, pp. 2:1-2:47, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@Article{bonte_et_al:TGDK.2.1.2, author = {Bonte, Pieter and Calbimonte, Jean-Paul and de Leng, Daniel and Dell'Aglio, Daniele and Della Valle, Emanuele and Eiter, Thomas and Giannini, Federico and Heintz, Fredrik and Schekotihin, Konstantin and Le-Phuoc, Danh and Mileo, Alessandra and Schneider, Patrik and Tommasini, Riccardo and Urbani, Jacopo and Ziffer, Giacomo}, title = {{Grounding Stream Reasoning Research}}, journal = {Transactions on Graph Data and Knowledge}, pages = {2:1--2:47}, ISSN = {2942-7517}, year = {2024}, volume = {2}, number = {1}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/TGDK.2.1.2}, URN = {urn:nbn:de:0030-drops-198597}, doi = {10.4230/TGDK.2.1.2}, annote = {Keywords: Stream Reasoning, Stream Processing, RDF streams, Streaming Linked Data, Continuous query processing, Temporal Logics, High-performance computing, Databases} }
Published in: LIPIcs, Volume 154, 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)
Taisuke Izumi, François Le Gall, and Frédéric Magniez. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 154, pp. 23:1-23:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{izumi_et_al:LIPIcs.STACS.2020.23, author = {Izumi, Taisuke and Le Gall, Fran\c{c}ois and Magniez, Fr\'{e}d\'{e}ric}, title = {{Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model}}, booktitle = {37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)}, pages = {23:1--23:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-140-5}, ISSN = {1868-8969}, year = {2020}, volume = {154}, editor = {Paul, Christophe and Bl\"{a}ser, Markus}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2020.23}, URN = {urn:nbn:de:0030-drops-118840}, doi = {10.4230/LIPIcs.STACS.2020.23}, annote = {Keywords: Quantum computing, distributed computing, CONGEST model} }
Published in: LIPIcs, Volume 132, 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)
Ran Duan, Ce Jin, and Hongxun Wu. Faster Algorithms for All Pairs Non-Decreasing Paths Problem. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 132, pp. 48:1-48:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{duan_et_al:LIPIcs.ICALP.2019.48, author = {Duan, Ran and Jin, Ce and Wu, Hongxun}, title = {{Faster Algorithms for All Pairs Non-Decreasing Paths Problem}}, booktitle = {46th International Colloquium on Automata, Languages, and Programming (ICALP 2019)}, pages = {48:1--48: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.48}, URN = {urn:nbn:de:0030-drops-106241}, doi = {10.4230/LIPIcs.ICALP.2019.48}, annote = {Keywords: graph optimization, matrix multiplication, non-decreasing paths} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Ran Duan, Yong Gu, and Le Zhang. Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 44:1-44:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{duan_et_al:LIPIcs.ICALP.2018.44, author = {Duan, Ran and Gu, Yong and Zhang, Le}, title = {{Improved Time Bounds for All Pairs Non-decreasing Paths in General Digraphs}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {44:1--44:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-076-7}, ISSN = {1868-8969}, year = {2018}, volume = {107}, editor = {Chatzigiannakis, Ioannis and Kaklamanis, Christos and Marx, D\'{a}niel and Sannella, Donald}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.44}, URN = {urn:nbn:de:0030-drops-90487}, doi = {10.4230/LIPIcs.ICALP.2018.44}, annote = {Keywords: Graph algorithms, Matrix multiplication, Non-decreasing paths} }