On-Line Algorithms, Bioinformatics, and SAT Solving

On-Line Algorithms, Bioinformatics, and SAT Solving (OLABS) is funded by a DKK 1,267,200.00 grant from the Danish Natural Science Research Council from January 1, 2011 through December 31, 2013.

Participants

PhD students

Jakob L. Andersen
Marie G. Christ
Magnus G. Find
Sushmita Gupta
Abyayananda Maiti
Philipp Peters

Environment

The project is carried out at the Department of Mathematics and Computer Science (IMADA) at the University of Southern Denmark. The group of participants are associated with the Research Training Program on Efficient Algorithms and High Quality Solutions.

Publications since January 1, 2011

Peer-Reviewed International Journal Articles

Inferring Chemical Reaction Patterns Using Rule Composition in Graph Grammars.: Jakob Lykke Andersen, Christoph Flamm, Daniel Merkle and Peter F Stadler.
Journal of Systems Chemistry. Accepted for publication.
A Practical O(n log² n) Time Algorithm for Computing the Triplet Distance on Binary Trees.: Andreas Sand, Gerth S. Brodal, Rolf Fagerberg, Christian N.S. Pedersen, Thomas Mailund.
BMC Bioinformatics. Accepted for publication.
A Technique for Exact Computation of Precoloring Extension on Interval Graphs.: Martin R. Ehmsen and Kim S. Larsen.
International Journal of Foundations of Computer Science, 24(1): 109-122, 2013.
Logic Minimization Techniques with Applications to Cryptology.: Joan Boyar and René Peralta.
Journal of Cryptology. 26: 280-312, 2013.
DOI: 10.1007/s00145-012-9124-7.
On the Absolute Approximation Ratio for First Fit and Related Results.: Joan Boyar, György Dósa, Leah Epstein.
Discrete Applied Mathematics, 160(13-14): 1914-1923, 2012.
CATCHprofiles: Clustering and Alighment Tool for ChIP Profiles.: Fiona G. G. Nielsen, Kasper G. Markus, Rune M. Friborg, Lene M. Favrholdt, Hendrik G. Stunnenberg, and Martijn Huynen
PLoS ONE, 7(1), 2012.
DOI:10.1371/journal.pone.0028272.
Maximizing Output and Recognizing Autocatalysis in Chemical Reaction Networks is NP-Complete.: J.L. Andersen, C. Flamm, D. Merkle and P.F. Stadler
Journal of System Chemistry, 3(1), 2012.
Swarm Controlled Emergence for Ant Clustering.: A. Scheidler, D. Merkle and M. Middendorf
Cybernetics, Accepted for publication.
Task Allocation in Organic Computing Systems: Networks with Reconfigurable Helper Units.: D. Merkle, M. Middendorf and A. Scheidler
Journal of Autonomous and Adaptive Communications Systems, Accepted for publication.
List Factoring and Relative Worst Order Analysis.: Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Algorithmica, 66(2): 287-309, 2013.
Comparing Online Algorithms for Bin Packing Problems.: Leah Epstein, Lene M. Favrholdt, and Jens S. Kohrt.
Journal of Scheduling, 15(1): 13-21, 2012.
DOI:10.1007/s10951-009-0129-5.
A New Variable-Sized Bin Packing Problem.: Joan Boyar and Lene M. Favrholdt.
Journal of Scheduling, 15(3):273-287, 2012.
Online Variable-Sized Bin Packing with Conflicts.: Leah Epstein, Lene M. Favrholdt, and Asaf Levin.
Discrete Optimization, 8(2): 333-343, 2011.
SAT Solving for Termination Proofs with Recursive Path Orders and Dependency Pairs.: Michael Codish, Jürgen Giesl, Peter Schneider-Kamp, René Thiemann.
Journal of Automated Reasoning, 49(1):53-93, 2011.
Proving Termination by Dependency Pairs and Inductive Theorem Proving.: Carsten Fuhs, Jürgen Giesl, Michael Parting, Peter Schneider-Kamp, and Stephan Swiderski.
Journal of Automated Reasoning, 47(2):133-160, 2011.
The Cost of Cache-Oblivious Searching.: Michael A. Bender, Gerth S. Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, and Alejandro López-Ortiz.
Algorithmica, 61(2):463-505, 2011.
Finding All Sorting Tandem Duplication Random Loss Operations.: M. Bernt, K.-Y. K.Y. Chen, M.C. Chen, A.-C. Chu, D. Merkle, H.-L. Wang, K.-M. Chao, and M. Middendorf.
Journal of Discrete Algorithms, 9(1):32-48, 2011.
Polytool: Polynomial Interpretations as a Basis for Termination Analysis of Logic Programs.: Manh Thang Nguyen, Danny De Schreye, Jürgen Giesl, and Peter Schneider-Kamp.
Theory and Practice of Logic Programming, 11(1): 33-63, 2011.
Automated Termination Proofs for Haskell by Term Rewriting.: Jürgen Giesl, Matthias Raffelsieper, Peter Schneider-Kamp, Stephan Swiderski, and René Thiemann.
ACM Transactions on Programming Languages and Systems, 33(2), 2011.

Peer-Reviewed International Conference Articles

Cancellation-Free Circuits in Unbounded and Bounded Depth.: Joan Boyar and Magnus Find.
In 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), Lecture Notes in Computer Science, 2013. Accepted for publication.
Performance Measures for Frequent Items in Online Streaming.: Joan Boyar, Kim Skak Larsen, and Abyayananda Maiti.
In 19th International Symposium on Fundamentals of Computation Theory (FCT 2013), Lecture Notes in Computer Science, 2013. Accepted for publication.
Relative Interval Analysis of Paging Algorithms on Access Graphs.: Joan Boyar, Sushmita Gupta, and Kim Skak Larsen.
In Algorithms and Data Structures Symposium (WADS 2013), Lecture Notes in Computer Science, 2013. Accepted for publication.
Four Measures of Nonlinearity.: Joan Boyar, Magnus Find, and René Peralta.
In 8th International Conference on Algorithms and Complexity (CIAC 2013), volume 7878 of Lecture Notes in Computer Science, pages 61-78, Springer 2013.
A Linear Operational Semantics for Termination and Complexity Analysis of ISO Prolog.: Thomas Ströder, Fabian Emmes, Peter Schneider-Kamp, Jürgen Giesl, and Carsten Fuhs.
In 21st International Symposium on Logic-Based Program Synthesis and Transformation, Lecture Notes in Computer Science. Accepted for publication.
Symbolic Evaluation Graphs and Term Rewriting - A General Methodology for Analyzing Logic Programs.: Jürgen Giesl, Thomas Ströder, Peter Schneider-Kamp, Fabian Emmes, and Carsten Fuhs.
In 14th International Symposium on Principles and Practice of Declarative Programming, Leuven, Belgium, pages 1-12, ACM Pres, 2012.
Efficient Algorithms for Computing the Triplet and Quartet Distance Between Trees of Arbitrary Degree.: Gerth S. Brodal, Rolf Fagerberg, Thomas Mailund, Christian N.S. Pedersen, Andreas Sand.
In Proceedings of 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 2013. Accepted for publication.
Towards Fair and Efficient Assignments of Students to Projects.: Marco Chiarandini, Rolf Fagerberg, Stefano Gualandi
In Proceedings of 9th International Conference on the Practice and Theory of Automated Timetabling (PATAT), pages 388-390, 2012.
Exploring Chemistry Using SMT.: Rolf Fagerberg, Daniel Merkle, Philipp Peters
In Proceedings of 18th International Conference on Principles and Practice of Constraint Programming (CP), volume 7514 of Lecture Notes in Computer Science, pages 900-915, Springer, 2012.
Competitive Routing on a Bounded-Degree Plane Spanner.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot.
In Proceedings of 24th Canadian Conference on Computational Geometry (CCCG), pages 285-290, 2012.
De-amortizing Binary Search Trees.: Prosenjit Bose, Rolf Fagerberg, Sébastien, Stefan Langerman
In Proceedings of 39th International Colloquium on Automata, Languages and Programming (ICALP), volume 7391 of Lecture Notes in Computer Science, pages 121-132, Springer, 2012.
On Plane Constrained Bounded-Degree Spanners.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot
In Proceedings of 10th Latin American Theoretical Informatics Symposium (LATIN), volume 7256 of LNCS, pages 85-96. Springer Verlag, 2012.
Competitive Routing in the Half-Theta-6-Graph.: Prosenjit Bose, Rolf Fagerberg, André van Renssen, Sander Verdonschot
In Proceedings of the Twenty-third Annual ACM-SIAM Symposium on Discrete Algorithms, 1319-1328, 2012.
Access Graphs Results for LRU versus FIFO under Relative Worst Order Analysis.: Joan Boyar, Sushmita Gupta and Kim S. Larsen.
In 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 7357 of Lecture Notes in Computer Science pages 328-339, Springer, 2012.
A Small Depth-16 Circuit for the AES S-Box.: Joan Boyar and René Peralta.
In Proceedings of IFIP SECURITY 2012. In Infomration Security and Privacy Research, 27th IFIP TC 11 Information Security and Privacy Conference, volume 376 of IFIP Advances in Information and Communication Technology, pages 287-298, Springer, 2012.
A Comparison of Performance Measures via Online Search.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In SIAM Joint FAW-AAIM Conference, volume 7285 of Lecture Notes in Computer Science, pages 303-314, Springer, 2012.
Dependency Triples for Improving Termination Analysis of Logic Programs with Cut.: Thomas Ströder, Peter Schneider-Kamp, and Jürgen Giesl.
In Twentieth International Symposium on Logic-Based Program Synthesis and Transformation, volume 6564 of Lecture Notes in Computer Science, 184-199, Springer, 2011.
List Factoring and Relative Worst Order Analysis.: Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
In Eighth Workshop on Approximation and Online Algorithms, volume 6534 of Lecture Notes in Computer Science, pages 118-129. Springer, 2011.
Optimal Base Encodings for Pseudo-Boolean Constraints.: Michael Codish, Yoav Fekete, Carsten Fuhs, and Peter Schneider-Kamp.
In 17th International Conference on Tools and Algorithms for the Construction and Analysis of Systems, volume 6605 of Lecture Notes in Computer Science, pages 189-204, Springer, 2011.

Books

Graph Edge Coloring: Vizing's Theorem and Goldberg's Conjecture.: Michael Stiebitz, Diego Scheide, Bjarne Toft, and Lene M. Favrholdt.
Wiley 2012.
(Swarm Intelligence - Introduction and Application, Chinese Translation).: C. Blum and D. Merkle (editors).
Chinese publisher: National Defense Industry Press with permission from Springer, 2011.

Book Contributions (entries, chapters, and editorials)

Ant Inspired Methods for Organic Computing.

Alexander Scheidler, Arne Brutschy, Konrad Diwold, Daniel Merkle, and Martin Middendorf.
In Organic Computing 2011, pages 95-109, 2011.

Patents

Method of Optimizing Combinational Circuits.: Joan Boyar and René Peralta. Patent No. US 8,316,338 B2, granted November 20, 2012.