Online Algorithms and Cheminformatics Meet Concurrency

	The project Online Algorithms and Cheminformatics Meet Concurrency is funded by the DKK 1,382,962 grant DFF-7014-00041 from the Independent Research Fund Denmark, Natural Sciences, running from July 1, 2017 through June 30, 2021.
	The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark.

Participants

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The participants are all associated with the Research Training Program in Computer Science as Ph.D. advisors.

Activities

Almost all activities on this grant are research related traveling to conferences, meetings by invitation, research collaboration, and hosting guests. We do not list the numerous conference travels or meetings by invitations, but only the longer research stays:

In the fall of 2017, Boyar & Larsen visited the theory group at the Department of Computer Science, University of Toronto, a group that includes prominent researchers of which Stephen Cook is known by all computer scientists. Boyar & Larsen worked with several people, including Allan Borodin, co-author of the leading textbook in online algorithms, and Faith Ellen - both ACM Fellows from 2014.

In the spring of 2019, Merkle visited Harvard University.

In January 2020, Fagerberg visited the algorithms group at Carleton University, Ottawa, Canada, hosted by Professor Jit Bose.

Publications

Here we list project publications since July 1, 2017. Slightly older publications can be found on the page for our previous project. Complete lists for each participant can be found via our individual home pages or via dblp, the standard search engine for Computer Science publications. We link to the official site for published papers using the doi (digital object identifier) of the papers. For open access versions, we refer to each author's own home page.

Acknowledgement: We are grateful to dblp (2021-08-18) for providing data for the publication list.

Peer-Reviewed International Journal Articles

Online Bin Covering with Advice.: Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen.
Algorithmica 83(3): 795-821, 2021.

Relative Worst-order Analysis: A Survey.: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
ACM Comput. Surv. 54(1): 8:1-8:21, 2021.

A Generic Framework for Engineering Graph Canonization Algorithms.: Jakob L. Andersen, Daniel Merkle.
ACM J. Exp. Algorithmics 25: 1-26, 2020.

Defining Autocatalysis in Chemical Reaction Networks.: Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
Journal of Systems Chemistry 8: 121-134, 2020.

Combining Graph Transformations and Semigroups for Isotopic Labeling Design.: Jakob Lykke Andersen, Daniel Merkle, Peter S. Rasmussen.
Journal of Computational Biology 27: 269-287, 2020.

Advice Complexity of Priority Algorithms.: Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov.
Theory Comput. Syst. 64(4): 593-625, 2020.

Randomized distributed online algorithms against adaptive offline adversaries.: Joan Boyar, Faith Ellen, Kim S. Larsen.
Inf. Process. Lett. 161: 105973, 2020.

A core model for choreographic programming.: Luís Cruz-Filipe, Fabrizio Montesi.
Theor. Comput. Sci. 802: 38-66, 2020.

Chemical Transformation Motifs - Modelling Pathways as Integer Hyperflows.: Jakob L. Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
IEEE ACM Trans. Comput. Biol. Bioinform. 16(2): 510-523, 2019.

On Plane Constrained Bounded-Degree Spanners.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
Algorithmica 81(4): 1392-1415, 2019.

Online Dominating Set.: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
Algorithmica 81(5): 1938-1964, 2019.

Tight Bounds for Restricted Grid Scheduling.: Joan Boyar, Faith Ellen.
Int. J. Found. Comput. Sci. 30(3): 375-405, 2019.

Small low-depth circuits for cryptographic applications.: Joan Boyar, Magnus Gausdal Find, René Peralta.
Cryptogr. Commun. 11(1): 109-127, 2019.

Handling preferences in student-project allocation.: Marco Chiarandini, Rolf Fagerberg, Stefano Gualandi.
Ann. Oper. Res. 275(1): 39-78, 2019.

Better late than never: a fully-abstract semantics for classical processes.: Wen Kokke, Fabrizio Montesi, Marco Peressotti.
Proc. ACM Program. Lang. 3(POPL): 24:1-24:29, 2019.

Towards Mechanistic Prediction of Mass Spectra Using Graph Transformation.: Jakob L. Andersen, Rolf Fagerberg, Christoph Flamm, Rojin Kianian, Daniel Merkle, Peter F. Stadler.
MATCH Communications in Mathematical and in Computer Chemistry 80: 705-731, 2018.

Continuous Yao graphs.: Davood Bakhshesh, Luis Barba, Prosenjit Bose, Jean-Lou De Carufel, Mirela Damian, Rolf Fagerberg, Mohammad Farshi, André van Renssen, Perouz Taslakian, Sander Verdonschot.
Comput. Geom. 67: 42-52, 2018.

Batch Coloring of Graphs.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
Algorithmica 80(11): 3293-3315, 2018.

Online-bounded analysis.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, Asaf Levin.
J. Sched. 21(4): 429-441, 2018.

Weighted Online Problems with Advice.: Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
Theory Comput. Syst. 62(6): 1443-1469, 2018.

Multiplicative complexity of vector valued Boolean functions.: Joan Boyar, Magnus Gausdal Find.
Theor. Comput. Sci. 720: 36-46, 2018.

Adding isolated vertices makes some greedy online algorithms optimal.: Joan Boyar, Christian Kudahl.
Discret. Appl. Math. 246: 12-21, 2018.

Choreographies, logically.: Marco Carbone, Fabrizio Montesi, Carsten Schürmann.
Distributed Comput. 31(1): 51-67, 2018.

Finding the K best synthesis plans.: Rolf Fagerberg, Christoph Flamm, Rojin Kianian, Daniel Merkle, Peter F. Stadler.
J. Cheminformatics 10(1): 19:1-19:21, 2018.

Online edge coloring of paths and trees with a fixed number of colors.: Lene M. Favrholdt, Jesper W. Mikkelsen.
Acta Informatica 55(1): 57-80, 2018.

DNA-templated synthesis optimization.: Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk.
Nat. Comput. 17(4): 693-707, 2018.

Time-consistent reconciliation maps and forbidden time travel.: Nikolai Nøjgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, Marc Hellmuth.
Algorithms Mol. Biol. 13(1): 2:1-2:17, 2018.

Competitive local routing with constraints.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
J. Comput. Geom. 8(1): 125-152, 2017.

The Advice Complexity of a Class of Hard Online Problems.: Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Jesper W. Mikkelsen.
Theory Comput. Syst. 61(4): 1128-1177, 2017.

Formally Proving Size Optimality of Sorting Networks.: Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp.
J. Autom. Reason. 59(4): 425-454, 2017.

Peer-Reviewed International Conference Articles

Fragile Complexity of Adaptive Algorithms.: Prosenjit Bose, Pilar Cano, Rolf Fagerberg, John Iacono, Riko Jacob, Stefan Langerman.
CIAC, Lecture Notes in Computer Science 12701: 144-157, Springer, 2021.
[Algorithms and Complexity - 12th International Conference, CIAC 2021, Virtual Event, May 10-12, 2021, Proceedings.]

An Experimental Study of External Memory Algorithms for Connected Components.: Gerth Stølting Brodal, Rolf Fagerberg, David Hammer, Ulrich Meyer, Manuel Penschuck, Hung Tran.
SEA, LIPIcs 190: 23:1-23:23, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[19th International Symposium on Experimental Algorithms, SEA 2021, June 7-9, 2021, Nice, France..]

Formalising a Turing-Complete Choreographic Language in Coq.: Luís Cruz-Filipe, Fabrizio Montesi, Marco Peressotti.
ITP, LIPIcs 193: 15:1-15:18, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[12th International Conference on Interactive Theorem Proving, ITP 2021, June 29 to July 1, 2021, Rome, Italy (Virtual Conference)..]

Jolie and LEMMA: Model-Driven Engineering and Programming Languages Meet on Microservices.: Saverio Giallorenzo, Fabrizio Montesi, Marco Peressotti, Florian Rademacher, Sabine Sachweh.
COORDINATION, Lecture Notes in Computer Science 12717: 276-284, Springer, 2021.
[Coordination Models and Languages - 23rd IFIP WG 6.1 International Conference, COORDINATION 2021, Held as Part of the 16th International Federated Conference on Distributed Computing Techniques, DisCoTec 2021, Valletta, Malta, June 14-18, 2021, Proceedings.]

Multiparty Languages: The Choreographic and Multitier Cases (Pearl).: Saverio Giallorenzo, Fabrizio Montesi, Marco Peressotti, David Richter, Guido Salvaneschi, Pascal Weisenburger.
ECOOP, LIPIcs 194: 22:1-22:27, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.
[35th European Conference on Object-Oriented Programming, ECOOP 2021, July 11-17, 2021, Aarhus, Denmark (Virtual Conference)..]

A Graph-Based Tool to Embed the π-Calculus into a Computational DPO Framework.: Jakob Lykke Andersen, Marc Hellmuth, Daniel Merkle, Nikolai Nøjgaard, Marco Peressotti.
SOFSEM (Doctoral Student Research Forum), CEUR Workshop Proceedings 2568: 121-132, CEUR-WS.org, 2020.
[Proceedings of the SOFSEM 2020 Doctoral Student Research Forum co-located with the 46th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2020), Limassol, Cyprus, January 20-24, 2020..]

The Servers of Serverless Computing: A Formal Revisitation of Functions as a Service.: Saverio Giallorenzo, Ivan Lanese, Fabrizio Montesi, Davide Sangiorgi, Stefano Pio Zingaro.
Gabbrielli's Festschrift, OASIcs 86: 5:1-5:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2020.
[Recent Developments in the Design and Implementation of Programming Languages, Gabbrielli's Festschrift, November 27, 2020, Bologna, Italy..]

Atom Tracking Using Cayley Graphs.: Marc Hellmuth, Daniel Merkle, Nikolai Nøjgaard.
ISBRA, Lecture Notes in Computer Science 12304: 406-415, Springer, 2020.
[Bioinformatics Research and Applications - 16th International Symposium, ISBRA 2020, Moscow, Russia, December 1-4, 2020, Proceedings.]

Fragile Complexity of Comparison-Based Algorithms.: Peyman Afshani, Rolf Fagerberg, David Hammer, Riko Jacob, Irina Kostitsyna, Ulrich Meyer, Manuel Penschuck, Nodari Sitchinava.
ESA, LIPIcs 144: 2:1-2:19, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
[27th Annual European Symposium on Algorithms, ESA 2019, September 9-11, 2019, Munich/Garching, Germany..]

Graph Transformations, Semigroups, and Isotopic Labeling.: Jakob L. Andersen, Daniel Merkle, Peter S. Rasmussen.
ISBRA, Lecture Notes in Computer Science 11490: 196-207, Springer, 2019.
[Bioinformatics Research and Applications - 15th International Symposium, ISBRA 2019, Barcelona, Spain, June 3-6, 2019, Proceedings.]

Online Bin Covering with Advice.: Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 11646: 225-238, Springer, 2019.
[Algorithms and Data Structures - 16th International Symposium, WADS 2019, Edmonton, AB, Canada, August 5-7, 2019, Proceedings.]

On Optimal Balance in B-Trees: What Does It Cost to Stay in Perfect Shape?: Rolf Fagerberg, David Hammer, Ulrich Meyer.
ISAAC, LIPIcs 149: 35:1-35:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2019.
[30th International Symposium on Algorithms and Computation, ISAAC 2019, December 8-11, 2019, Shanghai University of Finance and Economics, Shanghai, China..]

No More, No Less - A Formal Model for Serverless Computing.: Maurizio Gabbrielli, Saverio Giallorenzo, Ivan Lanese, Fabrizio Montesi, Marco Peressotti, Stefano Pio Zingaro.
COORDINATION, Lecture Notes in Computer Science 11533: 148-157, Springer, 2019.
[Coordination Models and Languages - 21st IFIP WG 6.1 International Conference, COORDINATION 2019, Held as Part of the 14th International Federated Conference on Distributed Computing Techniques, DisCoTec 2019, Kongens Lyngby, Denmark, June 17-21, 2019, Proceedings.]

Ephemeral Data Handling in Microservices.: Saverio Giallorenzo, Fabrizio Montesi, Larisa Safina, Stefano Pio Zingaro.
SCC: 234-236, IEEE, 2019.
[2019 IEEE International Conference on Services Computing, SCC 2019, Milan, Italy, July 8-13, 2019.]

A Generic Framework for Engineering Graph Canonization Algorithms.: Jakob L. Andersen, Daniel Merkle.
ALENEX: 139-153, SIAM, 2018.
[Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, LA, USA, January 7-8, 2018..]

Advice Complexity of Priority Algorithms.: Allan Borodin, Joan Boyar, Kim S. Larsen, Denis Pankratov.
WAOA, Lecture Notes in Computer Science 11312: 69-86, Springer, 2018.
[Approximation and Online Algorithms - 16th International Workshop, WAOA 2018, Helsinki, Finland, August 23-24, 2018, Revised Selected Papers.]

Relative Worst-Order Analysis: A Survey.: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen.
Adventures Between Lower Bounds and Higher Altitudes, Lecture Notes in Computer Science 11011: 216-230, Springer, 2018.
[Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday.]

Multiparty Classical Choreographies.: Marco Carbone, Luís Cruz-Filipe, Fabrizio Montesi, Agata Murawska.
LOPSTR, Lecture Notes in Computer Science 11408: 59-76, Springer, 2018.
[Logic-Based Program Synthesis and Transformation - 28th International Symposium, LOPSTR 2018, Frankfurt/Main, Germany, September 4-6, 2018, Revised Selected Papers.]

Communications in choreographies, revisited.: Luís Cruz-Filipe, Fabrizio Montesi, Marco Peressotti.
SAC: 1248-1255, ACM, 2018.
[Proceedings of the 33rd Annual ACM Symposium on Applied Computing, SAC 2018, Pau, France, April 09-13, 2018.]

Applied Choreographies.: Saverio Giallorenzo, Fabrizio Montesi, Maurizio Gabbrielli.
FORTE, Lecture Notes in Computer Science 10854: 21-40, Springer, 2018.
[Formal Techniques for Distributed Objects, Components, and Systems - 38th IFIP WG 6.1 International Conference, FORTE 2018, Held as Part of the 13th International Federated Conference on Distributed Computing Techniques, DisCoTec 2018, Madrid, Spain, June 18-21, 2018, Proceedings.]

Linear Time Canonicalization and Enumeration of Non-Isomorphic 1-Face Embeddings.: Marc Hellmuth, Anders S. Knudsen, Michal Kotrbcík, Daniel Merkle, Nikolai Nøjgaard.
ALENEX: 154-168, SIAM, 2018.
[Proceedings of the Twentieth Workshop on Algorithm Engineering and Experiments, ALENEX 2018, New Orleans, LA, USA, January 7-8, 2018..]

Heuristic Variants of A* Search for 3D Flight Planning.: Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
CPAIOR, Lecture Notes in Computer Science 10848: 361-376, Springer, 2018.
[Integration of Constraint Programming, Artificial Intelligence, and Operations Research - 15th International Conference, CPAIOR 2018, Delft, The Netherlands, June 26-29, 2018, Proceedings.]

Taking Linear Logic Apart.: Wen Kokke, Fabrizio Montesi, Marco Peressotti.
Linearity-TLLA@FLoC, EPTCS 292: 90-103, 2018.
[Proceedings Joint International Workshop on Linearity & Trends in Linear Logic and Applications, Linearity-TLLA@FLoC 2018, Oxford, UK, 7-8 July 2018..]

From the decorator pattern to circuit breakers in microservices.: Fabrizio Montesi, Janine Weber.
SAC: 1733-1735, ACM, 2018.
[Proceedings of the 33rd Annual ACM Symposium on Applied Computing, SAC 2018, Pau, France, April 09-13, 2018.]

Partial Homology Relations - Satisfiability in Terms of Di-Cographs.: Nikolai Nøjgaard, Nadia El-Mabrouk, Daniel Merkle, Nicolas Wieseke, Marc Hellmuth.
COCOON, Lecture Notes in Computer Science 10976: 403-415, Springer, 2018.
[Computing and Combinatorics - 24th International Conference, COCOON 2018, Qing Dao, China, July 2-4, 2018, Proceedings.]

Chemical Graph Transformation with Stereo-Information.: Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle, Peter F. Stadler.
ICGT, Lecture Notes in Computer Science 10373: 54-69, Springer, 2017.
[Graph Transformation - 10th International Conference, ICGT 2017, Held as Part of STAF 2017, Marburg, Germany, July 18-19, 2017, Proceedings.]

Relaxing the Irrevocability Requirement for Online Graph Algorithms.: Joan Boyar, Lene M. Favrholdt, Michal Kotrbcík, Kim S. Larsen.
WADS, Lecture Notes in Computer Science 10389: 217-228, Springer, 2017.
[Algorithms and Data Structures - 15th International Symposium, WADS 2017, St. John's, NL, Canada, July 31 - August 2, 2017, Proceedings.]

How to Get More Out of Your Oracles.: Luís Cruz-Filipe, Kim S. Larsen, Peter Schneider-Kamp.
ITP, Lecture Notes in Computer Science 10499: 164-170, Springer, 2017.
[Interactive Theorem Proving - 8th International Conference, ITP 2017, Brasília, Brazil, September 26-29, 2017, Proceedings.]

On Asynchrony and Choreographies.: Luís Cruz-Filipe, Fabrizio Montesi.
ICE@DisCoTec, EPTCS 261: 76-90, 2017.
[Proceedings 10th Interaction and Concurrency Experience, ICE@DisCoTec 2017, Neuchâtel, Switzerland, 21-22nd June 2017..]

DNA-Templated Synthesis Optimization.: Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk.
DNA, Lecture Notes in Computer Science 10467: 17-32, Springer, 2017.
[DNA Computing and Molecular Programming - 23rd International Conference, DNA 23, Austin, TX, USA, September 24-28, 2017, Proceedings.]

Flight Planning in Free Route Airspaces.: Casper Kehlet Jensen, Marco Chiarandini, Kim S. Larsen.
ATMOS, OASICS 59: 14:1-14:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
[17th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems, ATMOS 2017, September 7-8, 2017, Vienna, Austria.]

Constraint Handling in Flight Planning.: Anders Nicolai Knudsen, Marco Chiarandini, Kim S. Larsen.
CP, Lecture Notes in Computer Science 10416: 354-369, Springer, 2017.
[Principles and Practice of Constraint Programming - 23rd International Conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings.]

Forbidden Time Travel: Characterization of Time-Consistent Tree Reconciliation Maps.: Nikolai Nøjgaard, Manuela Geiß, Daniel Merkle, Peter F. Stadler, Nicolas Wieseke, Marc Hellmuth.
WABI, LIPIcs 88: 17:1-17:12, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.
[17th International Workshop on Algorithms in Bioinformatics, WABI 2017, August 21-23, 2017, Boston, MA, USA.]

Contributions by Invitation

Microservices: Yesterday, Today, and Tomorrow.: Nicola Dragoni, Saverio Giallorenzo, Alberto Lluch-Lafuente, Manuel Mazzara, Fabrizio Montesi, Ruslan Mustafin, Larisa Safina.
Present and Ulterior Software Engineering: 195-216, 2017.

Microservices: A Language-Based Approach.: Claudio Guidi, Ivan Lanese, Manuel Mazzara, Fabrizio Montesi.
Present and Ulterior Software Engineering: 217-225, 2017.

Data protection at SDU ▪ Databeskyttelse på SDU