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.

Another long-term visit is planned for Merkle at 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 for providing data for the publication list.

Peer-Reviewed International Journal Articles


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.

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.

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

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..]

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.]

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 fuer 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 fuer 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