Published in: LIPIcs, Volume 308, 32nd Annual European Symposium on Algorithms (ESA 2024)
Sebastian Angrick, Ben Bals, Tobias Friedrich, Hans Gawendowicz, Niko Hastrich, Nicolas Klodt, Pascal Lenzner, Jonas Schmidt, George Skretas, and Armin Wells. How to Reduce Temporal Cliques to Find Sparse Spanners. In 32nd Annual European Symposium on Algorithms (ESA 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 308, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{angrick_et_al:LIPIcs.ESA.2024.11, author = {Angrick, Sebastian and Bals, Ben and Friedrich, Tobias and Gawendowicz, Hans and Hastrich, Niko and Klodt, Nicolas and Lenzner, Pascal and Schmidt, Jonas and Skretas, George and Wells, Armin}, title = {{How to Reduce Temporal Cliques to Find Sparse Spanners}}, booktitle = {32nd Annual European Symposium on Algorithms (ESA 2024)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-338-6}, ISSN = {1868-8969}, year = {2024}, volume = {308}, editor = {Chan, Timothy and Fischer, Johannes and Iacono, John 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.2024.11}, URN = {urn:nbn:de:0030-drops-210822}, doi = {10.4230/LIPIcs.ESA.2024.11}, annote = {Keywords: Temporal Graphs, temporal Clique, temporal Spanner, Reachability, Graph Connectivity, Graph Sparsification} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Václav Blažej, Dušan Knop, Jan Pokorný, and Šimon Schierreich. Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 29:1-29:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{blazej_et_al:LIPIcs.MFCS.2024.29, author = {Bla\v{z}ej, V\'{a}clav and Knop, Du\v{s}an and Pokorn\'{y}, Jan and Schierreich, \v{S}imon}, title = {{Equitable Connected Partition and Structural Parameters Revisited: N-Fold Beats Lenstra}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {29:1--29:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.29}, URN = {urn:nbn:de:0030-drops-205857}, doi = {10.4230/LIPIcs.MFCS.2024.29}, annote = {Keywords: Equitable Connected Partition, structural parameters, fixed-parameter tractability, N-fold integer programming, tree-width, shrub-depth, modular-width} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Arnaud Casteigts, Nils Morawietz, and Petra Wolf. Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 36:1-36:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{casteigts_et_al:LIPIcs.MFCS.2024.36, author = {Casteigts, Arnaud and Morawietz, Nils and Wolf, Petra}, title = {{Distance to Transitivity: New Parameters for Taming Reachability in Temporal Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {36:1--36:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.36}, URN = {urn:nbn:de:0030-drops-205923}, doi = {10.4230/LIPIcs.MFCS.2024.36}, annote = {Keywords: Temporal graphs, Parameterized complexity, Reachability, Transitivity} }
Published in: LIPIcs, Volume 306, 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)
Jessica Enright, Samuel D. Hand, Laura Larios-Jones, and Kitty Meeks. Structural Parameters for Dense Temporal Graphs. In 49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 306, pp. 52:1-52:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{enright_et_al:LIPIcs.MFCS.2024.52, author = {Enright, Jessica and Hand, Samuel D. and Larios-Jones, Laura and Meeks, Kitty}, title = {{Structural Parameters for Dense Temporal Graphs}}, booktitle = {49th International Symposium on Mathematical Foundations of Computer Science (MFCS 2024)}, pages = {52:1--52:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-335-5}, ISSN = {1868-8969}, year = {2024}, volume = {306}, editor = {Kr\'{a}lovi\v{c}, Rastislav and Ku\v{c}era, Anton{\'\i}n}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2024.52}, URN = {urn:nbn:de:0030-drops-206082}, doi = {10.4230/LIPIcs.MFCS.2024.52}, annote = {Keywords: Graph algorithms, Parameterized Algorithms, Temporal Graphs} }
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)
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)
Konstantinos Dogeas, Thomas Erlebach, Frank Kammer, Johannes Meintrup, and William K. Moses Jr.. Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 297, pp. 55:1-55:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)
@InProceedings{dogeas_et_al:LIPIcs.ICALP.2024.55, author = {Dogeas, Konstantinos and Erlebach, Thomas and Kammer, Frank and Meintrup, Johannes and Moses Jr., William K.}, title = {{Exploiting Automorphisms of Temporal Graphs for Fast Exploration and Rendezvous}}, booktitle = {51st International Colloquium on Automata, Languages, and Programming (ICALP 2024)}, pages = {55:1--55: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.55}, URN = {urn:nbn:de:0030-drops-201989}, doi = {10.4230/LIPIcs.ICALP.2024.55}, annote = {Keywords: dynamic graphs, parameterized algorithms, algorithmic graph theory, graph automorphism, orbit number} }
Published in: LIPIcs, Volume 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)
Jessica Enright, Kitty Meeks, and Hendrik Molter. Counting Temporal Paths. In 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 254, pp. 30:1-30:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{enright_et_al:LIPIcs.STACS.2023.30, author = {Enright, Jessica and Meeks, Kitty and Molter, Hendrik}, title = {{Counting Temporal Paths}}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023)}, pages = {30:1--30:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-266-2}, ISSN = {1868-8969}, year = {2023}, volume = {254}, editor = {Berenbrink, Petra and Bouyer, Patricia and Dawar, Anuj and Kant\'{e}, Mamadou Moustapha}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2023.30}, URN = {urn:nbn:de:0030-drops-176829}, doi = {10.4230/LIPIcs.STACS.2023.30}, annote = {Keywords: Temporal Paths, Temporal Graphs, Parameterised Counting, Approximate Counting, #P-hard Counting Problems, Temporal Betweenness Centrality} }
Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)
Marco Bressan, Leslie Ann Goldberg, Kitty Meeks, and Marc Roth. Counting Subgraphs in Somewhere Dense Graphs. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 27:1-27:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{bressan_et_al:LIPIcs.ITCS.2023.27, author = {Bressan, Marco and Goldberg, Leslie Ann and Meeks, Kitty and Roth, Marc}, title = {{Counting Subgraphs in Somewhere Dense Graphs}}, booktitle = {14th Innovations in Theoretical Computer Science Conference (ITCS 2023)}, pages = {27:1--27:14}, 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.27}, URN = {urn:nbn:de:0030-drops-175304}, doi = {10.4230/LIPIcs.ITCS.2023.27}, annote = {Keywords: counting problems, somewhere dense graphs, parameterised complexity theory} }
Published in: LIPIcs, Volume 226, 11th International Conference on Fun with Algorithms (FUN 2022)
Samuel D. Hand, Jessica Enright, and Kitty Meeks. Making Life More Confusing for Firefighters. In 11th International Conference on Fun with Algorithms (FUN 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 226, pp. 15:1-15:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hand_et_al:LIPIcs.FUN.2022.15, author = {Hand, Samuel D. and Enright, Jessica and Meeks, Kitty}, title = {{Making Life More Confusing for Firefighters}}, booktitle = {11th International Conference on Fun with Algorithms (FUN 2022)}, pages = {15:1--15:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-232-7}, ISSN = {1868-8969}, year = {2022}, volume = {226}, editor = {Fraigniaud, Pierre and Uno, Yushi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2022.15}, URN = {urn:nbn:de:0030-drops-159851}, doi = {10.4230/LIPIcs.FUN.2022.15}, annote = {Keywords: Temporal graphs, Spreading processes, Parameterised complexity} }
Published in: LIPIcs, Volume 221, 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)
Samuel D. Hand, Jessica Enright, and Kitty Meeks. Brief Announcement: The Temporal Firefighter Problem. In 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 221, pp. 22:1-22:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
@InProceedings{hand_et_al:LIPIcs.SAND.2022.22, author = {Hand, Samuel D. and Enright, Jessica and Meeks, Kitty}, title = {{Brief Announcement: The Temporal Firefighter Problem}}, booktitle = {1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)}, pages = {22:1--22:3}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-224-2}, ISSN = {1868-8969}, year = {2022}, volume = {221}, editor = {Aspnes, James and Michail, Othon}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SAND.2022.22}, URN = {urn:nbn:de:0030-drops-159644}, doi = {10.4230/LIPIcs.SAND.2022.22}, annote = {Keywords: Temporal graphs, Spreading processes, Parameterised complexity} }
Published in: Dagstuhl Reports, Volume 11, Issue 3 (2021)
Arnaud Casteigts, Kitty Meeks, George B. Mertzios, and Rolf Niedermeier. Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171). In Dagstuhl Reports, Volume 11, Issue 3, pp. 16-46, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
@Article{casteigts_et_al:DagRep.11.3.16, author = {Casteigts, Arnaud and Meeks, Kitty and Mertzios, George B. and Niedermeier, Rolf}, title = {{Temporal Graphs: Structure, Algorithms, Applications (Dagstuhl Seminar 21171)}}, pages = {16--46}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2021}, volume = {11}, number = {3}, editor = {Casteigts, Arnaud and Meeks, Kitty and Mertzios, George B. and Niedermeier, Rolf}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/DagRep.11.3.16}, URN = {urn:nbn:de:0030-drops-146892}, doi = {10.4230/DagRep.11.3.16}, annote = {Keywords: algorithm engineering, complex network analysis, distributed computing, models and classes, parameterized complexity analysis} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Jessica Enright, Kitty Meeks, George B. Mertzios, and Viktor Zamaraev. Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{enright_et_al:LIPIcs.MFCS.2019.57, author = {Enright, Jessica and Meeks, Kitty and Mertzios, George B. and Zamaraev, Viktor}, title = {{Deleting Edges to Restrict the Size of an Epidemic in Temporal Networks}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-117-7}, ISSN = {1868-8969}, year = {2019}, volume = {138}, editor = {Rossmanith, Peter and Heggernes, Pinar and Katoen, Joost-Pieter}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2019.57}, URN = {urn:nbn:de:0030-drops-110010}, doi = {10.4230/LIPIcs.MFCS.2019.57}, annote = {Keywords: Temporal networks, spreading processes, graph modification, parameterised complexity} }
Published in: LIPIcs, Volume 115, 13th International Symposium on Parameterized and Exact Computation (IPEC 2018)
Kitty Meeks and Fiona Skerman. The Parameterised Complexity of Computing the Maximum Modularity of a Graph. In 13th International Symposium on Parameterized and Exact Computation (IPEC 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 115, pp. 9:1-9:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{meeks_et_al:LIPIcs.IPEC.2018.9, author = {Meeks, Kitty and Skerman, Fiona}, title = {{The Parameterised Complexity of Computing the Maximum Modularity of a Graph}}, booktitle = {13th International Symposium on Parameterized and Exact Computation (IPEC 2018)}, pages = {9:1--9:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-084-2}, ISSN = {1868-8969}, year = {2019}, volume = {115}, editor = {Paul, Christophe and Pilipczuk, Michal}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2018.9}, URN = {urn:nbn:de:0030-drops-102103}, doi = {10.4230/LIPIcs.IPEC.2018.9}, annote = {Keywords: modularity, community detection, integer quadratic programming, vertex cover, pathwidth} }
Published in: LIPIcs, Volume 63, 11th International Symposium on Parameterized and Exact Computation (IPEC 2016)
Kitty Meeks. Randomised Enumeration of Small Witnesses Using a Decision Oracle. In 11th International Symposium on Parameterized and Exact Computation (IPEC 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 63, pp. 22:1-22:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{meeks:LIPIcs.IPEC.2016.22, author = {Meeks, Kitty}, title = {{Randomised Enumeration of Small Witnesses Using a Decision Oracle}}, booktitle = {11th International Symposium on Parameterized and Exact Computation (IPEC 2016)}, pages = {22:1--22:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-023-1}, ISSN = {1868-8969}, year = {2017}, volume = {63}, editor = {Guo, Jiong and Hermelin, Danny}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.IPEC.2016.22}, URN = {urn:nbn:de:0030-drops-69218}, doi = {10.4230/LIPIcs.IPEC.2016.22}, annote = {Keywords: enumeration algorithms, parameterized complexity, randomized algorithms, color coding} }
Feedback for Dagstuhl Publishing