Published in: LIPIcs, Volume 248, 33rd International Symposium on Algorithms and Computation (ISAAC 2022)
Dibyayan Chakraborty, Antoine Dailly, Sandip Das, Florent Foucaud, Harmender Gahlawat, and Subir Kumar Ghosh. Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond. In 33rd International Symposium on Algorithms and Computation (ISAAC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 248, pp. 12:1-12:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2022)
@InProceedings{chakraborty_et_al:LIPIcs.ISAAC.2022.12, author = {Chakraborty, Dibyayan and Dailly, Antoine and Das, Sandip and Foucaud, Florent and Gahlawat, Harmender and Ghosh, Subir Kumar}, title = {{Complexity and Algorithms for ISOMETRIC PATH COVER on Chordal Graphs and Beyond}}, booktitle = {33rd International Symposium on Algorithms and Computation (ISAAC 2022)}, pages = {12:1--12:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-258-7}, ISSN = {1868-8969}, year = {2022}, volume = {248}, editor = {Bae, Sang Won and Park, Heejin}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2022.12}, URN = {urn:nbn:de:0030-drops-172974}, doi = {10.4230/LIPIcs.ISAAC.2022.12}, annote = {Keywords: Shortest paths, Isometric path cover, Chordal graph, Interval graph, AT-free graph, Approximation algorithm, FPT algorithm, Treewidth, Chordality, Treelength} }
Published in: LIPIcs, Volume 166, 34th European Conference on Object-Oriented Programming (ECOOP 2020)
Sam Van den Vonder, Thierry Renaux, Bjarno Oeyen, Joeri De Koster, and Wolfgang De Meuter. Tackling the Awkward Squad for Reactive Programming: The Actor-Reactor Model. In 34th European Conference on Object-Oriented Programming (ECOOP 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 166, pp. 19:1-19:29, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{vandenvonder_et_al:LIPIcs.ECOOP.2020.19, author = {Van den Vonder, Sam and Renaux, Thierry and Oeyen, Bjarno and De Koster, Joeri and De Meuter, Wolfgang}, title = {{Tackling the Awkward Squad for Reactive Programming: The Actor-Reactor Model}}, booktitle = {34th European Conference on Object-Oriented Programming (ECOOP 2020)}, pages = {19:1--19:29}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-154-2}, ISSN = {1868-8969}, year = {2020}, volume = {166}, editor = {Hirschfeld, Robert and Pape, Tobias}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2020.19}, URN = {urn:nbn:de:0030-drops-131768}, doi = {10.4230/LIPIcs.ECOOP.2020.19}, annote = {Keywords: functional reactive programming, reactive programming, reactive streams, actors, reactors} }
Published in: LIPIcs, Volume 141, 10th International Conference on Interactive Theorem Proving (ITP 2019)
Peter Lammich and Tobias Nipkow. Proof Pearl: Purely Functional, Simple and Efficient Priority Search Trees and Applications to Prim and Dijkstra. In 10th International Conference on Interactive Theorem Proving (ITP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 141, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{lammich_et_al:LIPIcs.ITP.2019.23, author = {Lammich, Peter and Nipkow, Tobias}, title = {{Proof Pearl: Purely Functional, Simple and Efficient Priority Search Trees and Applications to Prim and Dijkstra}}, booktitle = {10th International Conference on Interactive Theorem Proving (ITP 2019)}, pages = {23:1--23:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-122-1}, ISSN = {1868-8969}, year = {2019}, volume = {141}, editor = {Harrison, John and O'Leary, John and Tolmach, Andrew}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITP.2019.23}, URN = {urn:nbn:de:0030-drops-110788}, doi = {10.4230/LIPIcs.ITP.2019.23}, annote = {Keywords: Priority queue, Dijkstra’s algorithm, Prim’s algorithm, verification, Isabelle} }
Published in: LIPIcs, Volume 143, 19th International Workshop on Algorithms in Bioinformatics (WABI 2019)
Natalie Sauerwald, Yihang Shen, and Carl Kingsford. Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation. In 19th International Workshop on Algorithms in Bioinformatics (WABI 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 143, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{sauerwald_et_al:LIPIcs.WABI.2019.23, author = {Sauerwald, Natalie and Shen, Yihang and Kingsford, Carl}, title = {{Topological Data Analysis Reveals Principles of Chromosome Structure in Cellular Differentiation}}, booktitle = {19th International Workshop on Algorithms in Bioinformatics (WABI 2019)}, pages = {23:1--23:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-123-8}, ISSN = {1868-8969}, year = {2019}, volume = {143}, editor = {Huber, Katharina T. and Gusfield, Dan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2019.23}, URN = {urn:nbn:de:0030-drops-110537}, doi = {10.4230/LIPIcs.WABI.2019.23}, annote = {Keywords: topological data analysis, chromosome structure, Hi-C, topologically associating domains} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Wojciech Czerwiński, Sławomir Lasota, Christof Löding, and Radosław Piórkowski. New Pumping Technique for 2-Dimensional VASS. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 62:1-62:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{czerwinski_et_al:LIPIcs.MFCS.2019.62, author = {Czerwi\'{n}ski, Wojciech and Lasota, S{\l}awomir and L\"{o}ding, Christof and Pi\'{o}rkowski, Rados{\l}aw}, title = {{New Pumping Technique for 2-Dimensional VASS}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {62:1--62:14}, 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.62}, URN = {urn:nbn:de:0030-drops-110066}, doi = {10.4230/LIPIcs.MFCS.2019.62}, annote = {Keywords: vector addition systems with states, pumping, decidability} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Esther Galby, Paloma T. Lima, and Bernard Ries. Reducing the Domination Number of Graphs via Edge Contractions. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 41:1-41:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{galby_et_al:LIPIcs.MFCS.2019.41, author = {Galby, Esther and Lima, Paloma T. and Ries, Bernard}, title = {{Reducing the Domination Number of Graphs via Edge Contractions}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {41:1--41:13}, 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.41}, URN = {urn:nbn:de:0030-drops-109856}, doi = {10.4230/LIPIcs.MFCS.2019.41}, annote = {Keywords: domination number, blocker problem, graph classes} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Krishnendu Chatterjee, Thomas A. Henzinger, and Jan Otop. Long-Run Average Behavior of Vector Addition Systems with States. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 27:1-27:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{chatterjee_et_al:LIPIcs.CONCUR.2019.27, author = {Chatterjee, Krishnendu and Henzinger, Thomas A. and Otop, Jan}, title = {{Long-Run Average Behavior of Vector Addition Systems with States}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {27:1--27:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.27}, URN = {urn:nbn:de:0030-drops-109293}, doi = {10.4230/LIPIcs.CONCUR.2019.27}, annote = {Keywords: vector addition systems, mean-payoff, Diophantine inequalities} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Jérôme Leroux. Petri Net Reachability Problem (Invited Talk). In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 5:1-5:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{leroux:LIPIcs.MFCS.2019.5, author = {Leroux, J\'{e}r\^{o}me}, title = {{Petri Net Reachability Problem}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {5:1--5:3}, 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.5}, URN = {urn:nbn:de:0030-drops-109493}, doi = {10.4230/LIPIcs.MFCS.2019.5}, annote = {Keywords: Petri net, Reachability problem, Formal verification, Concurrency} }
Published in: LIPIcs, Volume 138, 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)
Serge Gaspers and Ray Li. Enumeration of Preferred Extensions in Almost Oriented Digraphs. In 44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 138, pp. 74:1-74:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{gaspers_et_al:LIPIcs.MFCS.2019.74, author = {Gaspers, Serge and Li, Ray}, title = {{Enumeration of Preferred Extensions in Almost Oriented Digraphs}}, booktitle = {44th International Symposium on Mathematical Foundations of Computer Science (MFCS 2019)}, pages = {74:1--74: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.74}, URN = {urn:nbn:de:0030-drops-110188}, doi = {10.4230/LIPIcs.MFCS.2019.74}, annote = {Keywords: abstract argumentation, exact algorithms, exponential time algorithms, parameterized algorithms, enumeration algorithms, semikernels in digraphs} }
Published in: LIPIcs, Volume 140, 30th International Conference on Concurrency Theory (CONCUR 2019)
Luís Caires, Jorge A. Pérez, Frank Pfenning, and Bernardo Toninho. Domain-Aware Session Types. In 30th International Conference on Concurrency Theory (CONCUR 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 140, pp. 39:1-39:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{caires_et_al:LIPIcs.CONCUR.2019.39, author = {Caires, Lu{\'\i}s and P\'{e}rez, Jorge A. and Pfenning, Frank and Toninho, Bernardo}, title = {{Domain-Aware Session Types}}, booktitle = {30th International Conference on Concurrency Theory (CONCUR 2019)}, pages = {39:1--39:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-121-4}, ISSN = {1868-8969}, year = {2019}, volume = {140}, editor = {Fokkink, Wan and van Glabbeek, Rob}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CONCUR.2019.39}, URN = {urn:nbn:de:0030-drops-109417}, doi = {10.4230/LIPIcs.CONCUR.2019.39}, annote = {Keywords: Session Types, Linear Logic, Process Calculi, Hybrid Logic} }
Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)
Rupak Majumdar, Marcus Pirron, Nobuko Yoshida, and Damien Zufferey. Motion Session Types for Robotic Interactions (Brave New Idea Paper). In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 28:1-28:27, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{majumdar_et_al:LIPIcs.ECOOP.2019.28, author = {Majumdar, Rupak and Pirron, Marcus and Yoshida, Nobuko and Zufferey, Damien}, title = {{Motion Session Types for Robotic Interactions}}, booktitle = {33rd European Conference on Object-Oriented Programming (ECOOP 2019)}, pages = {28:1--28:27}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-111-5}, ISSN = {1868-8969}, year = {2019}, volume = {134}, editor = {Donaldson, Alastair F.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.28}, URN = {urn:nbn:de:0030-drops-108205}, doi = {10.4230/LIPIcs.ECOOP.2019.28}, annote = {Keywords: Session Types, Robotics, Concurrent Programming, Motions, Communications, Multiparty Session Types, Deadlock Freedom} }
Published in: LIPIcs, Volume 134, 33rd European Conference on Object-Oriented Programming (ECOOP 2019)
Conrad Watt, Petar Maksimović, Neelakantan R. Krishnaswami, and Philippa Gardner. A Program Logic for First-Order Encapsulated WebAssembly. In 33rd European Conference on Object-Oriented Programming (ECOOP 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 134, pp. 9:1-9:30, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{watt_et_al:LIPIcs.ECOOP.2019.9, author = {Watt, Conrad and Maksimovi\'{c}, Petar and Krishnaswami, Neelakantan R. and Gardner, Philippa}, title = {{A Program Logic for First-Order Encapsulated WebAssembly}}, booktitle = {33rd European Conference on Object-Oriented Programming (ECOOP 2019)}, pages = {9:1--9:30}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-111-5}, ISSN = {1868-8969}, year = {2019}, volume = {134}, editor = {Donaldson, Alastair F.}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ECOOP.2019.9}, URN = {urn:nbn:de:0030-drops-108011}, doi = {10.4230/LIPIcs.ECOOP.2019.9}, annote = {Keywords: WebAssembly, program logic, separation logic, soundness, mechanisation} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Marthe Bonamy, Oscar Defrain, Marc Heinrich, and Jean-Florent Raymond. Enumerating Minimal Dominating Sets in Triangle-Free Graphs. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 16:1-16:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{bonamy_et_al:LIPIcs.STACS.2019.16, author = {Bonamy, Marthe and Defrain, Oscar and Heinrich, Marc and Raymond, Jean-Florent}, title = {{Enumerating Minimal Dominating Sets in Triangle-Free Graphs}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {16:1--16:12}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.16}, URN = {urn:nbn:de:0030-drops-102557}, doi = {10.4230/LIPIcs.STACS.2019.16}, annote = {Keywords: Enumeration algorithms, output-polynomial algorithms, minimal dominating set, triangle-free graphs, split graphs} }
Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)
Archontia C. Giannopoulou, O-joung Kwon, Jean-Florent Raymond, and Dimitrios M. Thilikos. Lean Tree-Cut Decompositions: Obstructions and Algorithms. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 32:1-32:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{giannopoulou_et_al:LIPIcs.STACS.2019.32, author = {Giannopoulou, Archontia C. and Kwon, O-joung and Raymond, Jean-Florent and Thilikos, Dimitrios M.}, title = {{Lean Tree-Cut Decompositions: Obstructions and Algorithms}}, booktitle = {36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)}, pages = {32:1--32:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-100-9}, ISSN = {1868-8969}, year = {2019}, volume = {126}, editor = {Niedermeier, Rolf and Paul, Christophe}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.32}, URN = {urn:nbn:de:0030-drops-102716}, doi = {10.4230/LIPIcs.STACS.2019.32}, annote = {Keywords: tree-cut width, lean decompositions, immersions, obstructions, parameterized algorithms} }
Published in: LIPIcs, Volume 112, 26th Annual European Symposium on Algorithms (ESA 2018)
Fedor V. Fomin, Petr A. Golovach, and Jean-Florent Raymond. On the Tractability of Optimization Problems on H-Graphs. In 26th Annual European Symposium on Algorithms (ESA 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 112, pp. 30:1-30:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)
@InProceedings{fomin_et_al:LIPIcs.ESA.2018.30, author = {Fomin, Fedor V. and Golovach, Petr A. and Raymond, Jean-Florent}, title = {{On the Tractability of Optimization Problems on H-Graphs}}, booktitle = {26th Annual European Symposium on Algorithms (ESA 2018)}, pages = {30:1--30:14}, 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.30}, URN = {urn:nbn:de:0030-drops-94930}, doi = {10.4230/LIPIcs.ESA.2018.30}, annote = {Keywords: H-topological intersection graphs, parameterized complexity, minimal separators, boolean-width, mim-width} }
Feedback for Dagstuhl Publishing