Published in: LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)
Matthew Johnson, Barnaby Martin, Sukanya Pandey, Daniël Paulusma, Siani Smith, and Erik Jan van Leeuwen. Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs. In 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 272, pp. 57:1-57:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)
@InProceedings{johnson_et_al:LIPIcs.MFCS.2023.57, author = {Johnson, Matthew and Martin, Barnaby and Pandey, Sukanya and Paulusma, Dani\"{e}l and Smith, Siani and van Leeuwen, Erik Jan}, title = {{Complexity Framework for Forbidden Subgraphs III: When Problems Are Tractable on Subcubic Graphs}}, booktitle = {48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023)}, pages = {57:1--57:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-292-1}, ISSN = {1868-8969}, year = {2023}, volume = {272}, editor = {Leroux, J\'{e}r\^{o}me and Lombardy, Sylvain and Peleg, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.57}, URN = {urn:nbn:de:0030-drops-185914}, doi = {10.4230/LIPIcs.MFCS.2023.57}, annote = {Keywords: forbidden subgraphs, independent feedback vertex set, treewidth} }
Published in: LIPIcs, Volume 161, 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)
Patty Commins, David Liben-Nowell, Tina Liu, and Kiran Tomlinson. Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions. In 31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 161, pp. 11:1-11:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
@InProceedings{commins_et_al:LIPIcs.CPM.2020.11, author = {Commins, Patty and Liben-Nowell, David and Liu, Tina and Tomlinson, Kiran}, title = {{Summarizing Diverging String Sequences, with Applications to Chain-Letter Petitions}}, booktitle = {31st Annual Symposium on Combinatorial Pattern Matching (CPM 2020)}, pages = {11:1--11:15}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-149-8}, ISSN = {1868-8969}, year = {2020}, volume = {161}, editor = {G{\o}rtz, Inge Li and Weimann, Oren}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CPM.2020.11}, URN = {urn:nbn:de:0030-drops-121367}, doi = {10.4230/LIPIcs.CPM.2020.11}, annote = {Keywords: edit distance, tree reconstruction, information propagation, chain letters} }
Published in: LIPIcs, Volume 144, 27th Annual European Symposium on Algorithms (ESA 2019)
Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck, and Nodari Sitchinava. Fragile Complexity of Comparison-Based Algorithms. In 27th Annual European Symposium on Algorithms (ESA 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 144, pp. 2:1-2:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)
@InProceedings{afshani_et_al:LIPIcs.ESA.2019.2, author = {Afshani, Peyman and Fagerberg, Rolf and Hammer, David and Jacob, Riko and Kostitsyna, Irina and Meyer, Ulrich and Penschuck, Manuel and Sitchinava, Nodari}, title = {{Fragile Complexity of Comparison-Based Algorithms}}, booktitle = {27th Annual European Symposium on Algorithms (ESA 2019)}, pages = {2:1--2:19}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-124-5}, ISSN = {1868-8969}, year = {2019}, volume = {144}, editor = {Bender, Michael A. and Svensson, Ola and Herman, Grzegorz}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2019.2}, URN = {urn:nbn:de:0030-drops-111235}, doi = {10.4230/LIPIcs.ESA.2019.2}, annote = {Keywords: Algorithms, comparison based algorithms, lower bounds} }
Published in: LIPIcs, Volume 116, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)
Corrie Jacobien Carstens and Pieter Kleer. Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 116, pp. 36:1-36:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{carstens_et_al:LIPIcs.APPROX-RANDOM.2018.36, author = {Carstens, Corrie Jacobien and Kleer, Pieter}, title = {{Speeding up Switch Markov Chains for Sampling Bipartite Graphs with Given Degree Sequence}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2018)}, pages = {36:1--36:18}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-085-9}, ISSN = {1868-8969}, year = {2018}, volume = {116}, editor = {Blais, Eric and Jansen, Klaus and D. P. Rolim, Jos\'{e} and Steurer, David}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2018.36}, URN = {urn:nbn:de:0030-drops-94403}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2018.36}, annote = {Keywords: Binary matrix, graph sampling, Curveball, switch, Markov chain decomposition, Johnson graph} }
Published in: LIPIcs, Volume 107, 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)
Juan Jose Besa, William E. Devanny, David Eppstein, Michael T. Goodrich, and Timothy Johnson. Optimally Sorting Evolving Data. In 45th International Colloquium on Automata, Languages, and Programming (ICALP 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 107, pp. 81:1-81:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)
@InProceedings{besa_et_al:LIPIcs.ICALP.2018.81, author = {Besa, Juan Jose and Devanny, William E. and Eppstein, David and Goodrich, Michael T. and Johnson, Timothy}, title = {{Optimally Sorting Evolving Data}}, booktitle = {45th International Colloquium on Automata, Languages, and Programming (ICALP 2018)}, pages = {81:1--81:13}, 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-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2018.81}, URN = {urn:nbn:de:0030-drops-90858}, doi = {10.4230/LIPIcs.ICALP.2018.81}, annote = {Keywords: Sorting, Evolving data, Insertion sort} }
Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)
Giordano Da Lozzo, William E. Devanny, David Eppstein, and Timothy Johnson. Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 24:1-24:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
@InProceedings{dalozzo_et_al:LIPIcs.ISAAC.2017.24, author = {Da Lozzo, Giordano and Devanny, William E. and Eppstein, David and Johnson, Timothy}, title = {{Square-Contact Representations of Partial 2-Trees and Triconnected Simply-Nested Graphs}}, booktitle = {28th International Symposium on Algorithms and Computation (ISAAC 2017)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-054-5}, ISSN = {1868-8969}, year = {2017}, volume = {92}, editor = {Okamoto, Yoshio and Tokuyama, Takeshi}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.24}, URN = {urn:nbn:de:0030-drops-82675}, doi = {10.4230/LIPIcs.ISAAC.2017.24}, annote = {Keywords: Square-Contact Representations, Partial 2-Trees, Simply-Nested Graphs} }
Published in: Dagstuhl Reports, Volume 6, Issue 3 (2016)
Daniel Delling, Camil Demetrescu, David S. Johnson, and Jan Vitek. Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111). In Dagstuhl Reports, Volume 6, Issue 3, pp. 24-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
@Article{delling_et_al:DagRep.6.3.24, author = {Delling, Daniel and Demetrescu, Camil and Johnson, David S. and Vitek, Jan}, title = {{Rethinking Experimental Methods in Computing (Dagstuhl Seminar 16111)}}, pages = {24--43}, journal = {Dagstuhl Reports}, ISSN = {2192-5283}, year = {2016}, volume = {6}, number = {3}, editor = {Delling, Daniel and Demetrescu, Camil and Johnson, David S. and Vitek, Jan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagRep.6.3.24}, URN = {urn:nbn:de:0030-drops-61463}, doi = {10.4230/DagRep.6.3.24}, annote = {Keywords: Algorithms, Benchmarks, Data sets, Experiments, Repeatability, Reproducibility, Software Artifacts, Statistics} }
Published in: LIPIcs, Volume 28, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)
Josep Díaz, Leslie Ann Goldberg, David Richerby, and Maria Serna. Absorption Time of the Moran Process. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 28, pp. 630-642, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)
@InProceedings{diaz_et_al:LIPIcs.APPROX-RANDOM.2014.630, author = {D{\'\i}az, Josep and Goldberg, Leslie Ann and Richerby, David and Serna, Maria}, title = {{Absorption Time of the Moran Process}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2014)}, pages = {630--642}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-939897-74-3}, ISSN = {1868-8969}, year = {2014}, volume = {28}, editor = {Jansen, Klaus and Rolim, Jos\'{e} and Devanur, Nikhil R. and Moore, Cristopher}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2014.630}, URN = {urn:nbn:de:0030-drops-47279}, doi = {10.4230/LIPIcs.APPROX-RANDOM.2014.630}, annote = {Keywords: Moran Process} }
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-dev.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: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)
Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders. 10261 Abstracts Collection – Algorithm Engineering. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{italiano_et_al:DagSemProc.10261.1, author = {Italiano, Giuseppe F. and Johnson, David S. and Mutzel, Petra and Sanders, Peter}, title = {{10261 Abstracts Collection – Algorithm Engineering}}, booktitle = {Algorithm Engineering}, pages = {1--10}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10261}, editor = {Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.1}, URN = {urn:nbn:de:0030-drops-28179}, doi = {10.4230/DagSemProc.10261.1}, annote = {Keywords: Experimental algorithmics, Game theory, Parallel and distributed algorithms, Multi-core} }
Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)
Giuseppe F. Italiano, David S. Johnson, Petra Mutzel, and Peter Sanders. 10261 Executive Summary – Algorithm Engineering. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-2, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{italiano_et_al:DagSemProc.10261.2, author = {Italiano, Giuseppe F. and Johnson, David S. and Mutzel, Petra and Sanders, Peter}, title = {{10261 Executive Summary – Algorithm Engineering}}, booktitle = {Algorithm Engineering}, pages = {1--2}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10261}, editor = {Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.2}, URN = {urn:nbn:de:0030-drops-27966}, doi = {10.4230/DagSemProc.10261.2}, annote = {Keywords: Experimental algorithmics, Game theory, Parallel and distributed algorithms, Multi-core} }
Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)
Ahmed Abousamra, David P. Bunde, and Kirk Pruhs. An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{abousamra_et_al:DagSemProc.10261.3, author = {Abousamra, Ahmed and Bunde, David P. and Pruhs, Kirk}, title = {{An Experimental Comparison of Speed Scaling Algorithms with Deadline Feasibility Constraints}}, booktitle = {Algorithm Engineering}, pages = {1--22}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10261}, editor = {Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.3}, URN = {urn:nbn:de:0030-drops-27971}, doi = {10.4230/DagSemProc.10261.3}, annote = {Keywords: Scheduling, Speed Scaling, Experimental Algorithms, Power Management} }
Published in: Dagstuhl Seminar Proceedings, Volume 10261, Algorithm Engineering (2010)
Henning Meyerhenke and Joachim Gehweiler. On Dynamic Graph Partitioning and Graph Clustering using Diffusion. In Algorithm Engineering. Dagstuhl Seminar Proceedings, Volume 10261, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2010)
@InProceedings{meyerhenke_et_al:DagSemProc.10261.4, author = {Meyerhenke, Henning and Gehweiler, Joachim}, title = {{On Dynamic Graph Partitioning and Graph Clustering using Diffusion}}, booktitle = {Algorithm Engineering}, pages = {1--19}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2010}, volume = {10261}, editor = {Giuseppe F. Italiano and David S. Johnson and Petra Mutzel and Peter Sanders}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.10261.4}, URN = {urn:nbn:de:0030-drops-27980}, doi = {10.4230/DagSemProc.10261.4}, annote = {Keywords: Dynamic graph partitioning/clustering, disturbed diffusion, load balancing, relaxed cut optimization} }
Published in: Dagstuhl Seminar Proceedings, Volume 6121, Atomicity: A Unifying Concept in Computer Science (2006)
Calton Pu, Jim Johnson, Rogerio de Lemos, Andreas Reuter, David Taylor, and Irfan Zakiuddin. 06121 Report: Break Out Session on Guaranteed Execution. In Atomicity: A Unifying Concept in Computer Science. Dagstuhl Seminar Proceedings, Volume 6121, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2006)
@InProceedings{pu_et_al:DagSemProc.06121.3, author = {Pu, Calton and Johnson, Jim and de Lemos, Rogerio and Reuter, Andreas and Taylor, David and Zakiuddin, Irfan}, title = {{06121 Report: Break Out Session on Guaranteed Execution}}, booktitle = {Atomicity: A Unifying Concept in Computer Science}, series = {Dagstuhl Seminar Proceedings (DagSemProc)}, ISSN = {1862-4405}, year = {2006}, volume = {6121}, editor = {Clifford B. Jones and David Lomet and Alexander Romanovsky and Gerhard Weikum}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemProc.06121.3}, URN = {urn:nbn:de:0030-drops-6410}, doi = {10.4230/DagSemProc.06121.3}, annote = {Keywords: Guaranteed properties, declarative specifications, generation of workflow program, generation of invariant guards, automated failure analysis, automat} }
Published in: Dagstuhl Seminar Reports. Dagstuhl Seminar Reports, Volume 1 (2021)
David S. Johnson, Jan Karel Lenstra, and Gerhard J. Woeginger. The Travelling Salesman Problem (Dagstuhl Seminar 02261). Dagstuhl Seminar Report 346, pp. 1-17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2004)
@TechReport{johnson_et_al:DagSemRep.346, author = {Johnson, David S. and Lenstra, Jan Karel and Woeginger, Gerhard J.}, title = {{The Travelling Salesman Problem (Dagstuhl Seminar 02261)}}, pages = {1--17}, ISSN = {1619-0203}, year = {2004}, type = {Dagstuhl Seminar Report}, number = {346}, institution = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops-dev.dagstuhl.de/entities/document/10.4230/DagSemRep.346}, URN = {urn:nbn:de:0030-drops-152271}, doi = {10.4230/DagSemRep.346}, }
Feedback for Dagstuhl Publishing