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, 2020.
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.

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.

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 (2020-02-16) for providing data for the publication list.

Peer-Reviewed International Journal Articles

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. Biology 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.
Cryptography and Communications 11(1): 109-127, 2019.

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

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

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. Scheduling 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.
Discrete Applied Mathematics 246: 12-21, 2018.

Choreographies, logically.
Marco Carbone, Fabrizio Montesi, Carsten Schürmann.
Distributed Computing 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 Inf. 55(1): 57-80, 2018.

DNA-templated synthesis optimization.
Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, Alexei Mihalchuk.
Natural Computing 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 for Molecular Biology 13(1): 2:1-2:17, 2018.

Competitive local routing with constraints.
Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
JoCG 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. Reasoning 59(4): 425-454, 2017.

Peer-Reviewed International Conference Articles

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 SDUDatabeskyttelse på SDU