Papers authored by Kim S. Larsen

Final versions of most papers can be obtained from the home pages for the various journals and series. Direct links are given for almost all papers below; click on the title to find the abstract and a link to the publisher's version. If you have difficulty obtaining a copy of one of my papers, then please send me an e-mail. References on this page are also available in BibTeX and pdf. You can also use the listing from dblp (book contributions, papers which are to appear, and very recently published papers cannot be found via the dblp listing).

Notation: Using separate counters for

- Peer-Reviewed International Journal Articles

- Peer-Reviewed International Conference Articles

- Contributions by Invitation

2024
[j59]
Online Unit Profit Knapsack with Untrusted Predictions.: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
Algorithmica, 86: 2786-2821, 2024.
[j58]
Advice Complexity of Adaptive Priority Algorithms.: Joan Boyar, Kim S. Larsen, and Denis Pankratov.
Theoretical Computer Science, 984(114318):1-31, 2024.
[c54]
On the Online Weighted Non-Crossing Matching Problem.: Joan Boyar, Shahin Kamali, Kim S. Larsen, Ali Mohammad Lavasani, Yaqiao Li, and Denis Pankratov.
In 19th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 294 of Leibniz International Proceedings in Informatics (LIPIcs), pages 16:1-16:19. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2024.
2023
[c53]
Quotable Signatures for Authenticating Shared Quotes.: Joan Boyar, Simon Erfurth, Kim S. Larsen, and Ruben Niederhagen.
In 8th International Conference on Cryptology and Information Security in Latin America (LATINCRYPT), volume 14168 of Lecture Notes in Computer Science, pages 273-292. Springer, 2023.
[c52]
Paging with Succinct Predictions.: Antonios Antoniadis, Joan Boyar, Marek Eliáš, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, and Bertrand Simon.
In 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 952-968. PMLR, 2023.
[c51]
Online Minimum Spanning Trees with Weight Predictions.: Magnus Berg, Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
In 18th International Algorithms and Data Structures Symposium (WADS), volume 14079 of Lecture Notes in Computer Science, pages 136-148. Springer, 2023.
[c50]
Online Interval Scheduling with Predictions.: Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen.
In 18th International Algorithms and Data Structures Symposium (WADS), volume 14079 of Lecture Notes in Computer Science, pages 193-207. Springer, 2023.
2022
[j57]
Relaxing the Irrevocability Requirement for Online Graph Algorithms.: Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen.
Algorithmica, 84(7):1916-1951, 2022.
[c49]
Online Unit Profit Knapsack with Untrusted Predictions.: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
In 18th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 227 of Leibniz International Proceedings in Informatics (LIPIcs), pages 20:1-20:17. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2022.
2021
[j56]
Online Bin Covering with Advice.: Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen.
Algorithmica, 83(3): 795-821, 2021.
[j55]
Relative Worst-Order Analysis: A Survey.: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
ACM Computing Surveys, 54(1):1-21, 2021. Article No. 8.
2020
[j54]
Randomized Distributed Online Algorithms Against Adaptive Offline Adversaries.: Joan Boyar, Faith Ellen, and Kim S. Larsen.
Information Processing Letters, 161: Article No. 105973, 2020.
[j53]
Advice Complexity of Priority Algorithms.: Allan Borodin, Joan Boyar, Kim S. Larsen, and Denis Pankratov.
Theory of Computing Systems, 64(4): 593-625, 2020.
2019
[j52]
Online Dominating Set.: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen.
Algorithmica, 81(5):1938-1964, 2019.
[c48]
Online Bin Covering with Advice.: Joan Boyar, Lene M. Favrholdt, Shahin Kamali, and Kim S. Larsen.
In 16th International Algorithms and Data Structures Symposium (WADS), volume 11646 of Lecture Notes in Computer Science, pages 225-238. Springer, 2019.
2018
[j51]
DNA-Templated Synthesis Optimization.: Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, and Alexei Mihalchuk.
Natural Computing, 17(4): 693-707, 2018.
[j50]
Batch Coloring of Graphs.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
Algorithmica, 80(11): 3293-3315, 2018.
[j49]
Online-Bounded Analysis.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
Journal of Scheduling, 21(4): 429-441, 2018.
[c47]
Advice Complexity of Priority Algorithms.: Allan Borodin, Joan Boyar, Kim S. Larsen, and Denis Pankratov.
In 16th Workshop on Approximation and Online Algorithms (WAOA), volume 11312 of Lecture Notes in Computer Science, pages 69-86. Springer, 2018.
[c46]
Heuristic Variants for A* Search in 3D Flight Planning.: Anders N. Knudsen, Marco Chiarandini, and Kim S. Larsen.
In 15th International Conference on the Integration of Constraint Programming, Artificial Intelligence, and Operations Research (CPAIOR), volume 10848 of Lecture Notes in Computer Science, pages 361-376. Springer, 2018.
[i4]
Relative Worst-Order Analysis: A Survey.: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
In Adventures Between Lower Bounds and Higher Altitudes - Essays Dedicated to Juraj Hromkovič on the Occasion of His 60th Birthday, volume 11011 of Lecture Notes in Computer Science, pages 216-230. Springer, 2018.
2017
[j48]
Formally Proving Size Optimality of Sorting Networks.: Luís Cruz-Filipe, Kim S. Larsen, and Peter Schneider-Kamp.
Journal of Automated Reasoning, 59(4): 425-454, 2017.
[j47]
Online Algorithms with Advice: A Survey.: Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen.
ACM Computing Surveys, 50(2):1-34, 2017. Article No. 19.
[j46]
On the List Update Problem with Advice.: Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
Information and Computation, 253(3): 411-423, 2017.
[c45]
Constraint Handling in Flight Planning.: Anders N. Knudsen, Marco Chiarandini, and Kim S. Larsen.
In 23rd International Conference on Principles and Practice of Constraint Programming (CP), volume 10416 of Lecture Notes in Computer Science, pages 354-369. Springer, 2017.
[c44]
How to Get More Out of Your Oracles.: Luís Cruz-Filipe, Kim S. Larsen, and Peter Schneider-Kamp.
In 8th International Conference on Interactive Theorem Proving (ITP), volume 10499 of Lecture Notes in Computer Science, pages 164-170. Springer, 2017.
[c43]
DNA-Templated Synthesis Optimization.: Bjarke N. Hansen, Kim S. Larsen, Daniel Merkle, and Alexei Mihalchuk.
In 23rd International Conference on DNA Computing and Molecular Programming (DNA), volume 10467 of Lecture Notes in Computer Science, pages 17-32. Springer, 2017.
[c42]
Flight Planning in Free Route Airspaces.: Casper Kehlet Jensen, Marco Chiarandini, and Kim S. Larsen.
In 17th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS), volume 59 of OASIcs, pages 14:1-14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2017.
[c41]
Relaxing the Irrevocability Requirement for Online Graph Algorithms.: Joan Boyar, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen.
In 15th International Algorithms and Data Structures Symposium (WADS), volume 10389 of Lecture Notes in Computer Science, pages 217-228. Springer, 2017.
[c40]
The Paths to Choreography Extraction.: Luís Cruz-Filipe, Kim S. Larsen, and Fabrizio Montesi.
In 20th International Conference on Foundations of Software Science and Computation Structures (FoSSaCS), volume 10203 of Lecture Notes in Computer Science, pages 424-440. Springer, 2017.
[c39]
Batch Coloring of Graphs.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
In 14th Workshop on Approximation and Online Algorithms (WAOA), volume 10138 of Lecture Notes in Computer Science, pages 52-64. Springer, 2017.
2016
[j45]
Online Bin Packing with Advice.: Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
Algorithmica, 74(1): 507-527, 2016.
[c38]
Vertical Optimization of Resource Dependent Flight Paths.: Anders N. Knudsen, Marco Chiarandini, and Kim S. Larsen.
In 22nd European Conference on Artificial Intelligence (ECAI), volume 285 of Frontiers in Artificial Intelligence and Applications, pages 639-645. IOS Press, 2016.
[c37]
Online Dominating Set.: Joan Boyar, Stephan J. Eidenbenz, Lene M. Favrholdt, Michal Kotrbčík, and Kim S. Larsen.
In 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 53 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2016.
[c36]
Online Bounded Analysis.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Asaf Levin.
In 11th International Computer Science Symposium in Russia (CSR), volume 9691 of Lecture Notes in Computer Science, pages 131-145. Springer, 2016.
[i3]
Online Algorithms with Advice: A Survey.: Joan Boyar, Lene M. Favrholdt, Christian Kudahl, Kim S. Larsen, and Jesper W. Mikkelsen.
ACM SIGACT News, 47(3): 93-129, 2016.
2015
[j44]
Soccer Is Harder than Football.: Jan Christensen, Anders Nicolai Knudsen, and Kim S. Larsen.
International Journal of Foundations of Computer Science, 26(4): 477-486, 2015.
[j43]
The Frequent Items Problem in Online Streaming under Various Performance Measures.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
International Journal of Foundations of Computer Science, 26(4): 413-439, 2015.
[j42]
Online Multi-Coloring with Advice.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Theoretical Computer Science, 596: 79-91, 2015.
[j41]
A Comparison of Performance Measures for Online Algorithms.: Joan Boyar, Sandy Irani, and Kim S. Larsen.
Algorithmica, 72(4): 969-994, 2015.
[j40]
Relative Interval Analysis of Paging Algorithms on Access Graphs.: Joan Boyar, Sushmita Gupta, and Kim S. Larsen.
Theoretical Computer Science, 568: 28-48, 2015.
[c35]
Online Multi-Coloring with Advice.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
In 12th Workshop on Approximation and Online Algorithms (WAOA), volume 8952 of Lecture Notes in Computer Science, pages 83-94. Springer, 2015.
2014
[j39]
Online Bin Covering: Expectations vs. Guarantees.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Theoretical Computer Science, 556: 71-84, 2014.
[j38]
A Comparison of Performance Measures via Online Search.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
Theoretical Computer Science, 532: 2-13, 2014.
[c34]
Online Bin Packing with Advice.: Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
In 31st International Symposium on Theoretical Aspects of Computer Science (STACS), volume 25 of Leibniz International Proceedings in Informatics (LIPIcs), pages 174-186. Schloss Dagstuhl - Leibniz-Zentrum für Informatik GmbH, 2014.
[c33]
On the List Update Problem with Advice.: Joan Boyar, Shahin Kamali, Kim S. Larsen, and Alejandro López-Ortiz.
In 8th International Conference on Language and Automata Theory and Applications (LATA), volume 8370 of Lecture Notes in Computer Science, pages 210-221. Springer, 2014.
2013
[j37]
Online Multi-Coloring on the Path Revisited.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
Acta Informatica, 50(5-6): 343-357, 2013.
[j36]
Better Bounds on Online Unit Clustering.: Martin R. Ehmsen and Kim S. Larsen.
Theoretical Computer Science, 500:1-24, 2013.
[j35]
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.
[j34]
List Factoring and Relative Worst Order Analysis.: Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Algorithmica, 66(2): 287-309, 2013.
[c32]
Online Bin Covering: Expectations vs. Guarantees.: Marie G. Christ, Lene M. Favrholdt, and Kim S. Larsen.
In 7th Annual International Conference on Combinatorial Optimization and Applications (COCOA), volume 8287 of Lecture Notes in Computer Science, pages 226-237. Springer, 2013.
[c31]
The Frequent Items Problem in Online Streaming under Various Performance Measures.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In 19th International Symposium on Fundamentals of Computation Theory (FCT), volume 8070 of Lecture Notes in Computer Science, pages 60-71. Springer, 2013.
[c30]
Relative Interval Analysis of Paging Algorithms on Access Graphs.: Joan Boyar, Sushmita Gupta, and Kim S. Larsen.
In 13th International Algorithms and Data Structures Symposium (WADS), volume 8037 of Lecture Notes in Computer Science, pages 195-206. Springer, 2013.
2012
[c29]
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.
[c28]
A Comparison of Performance Measures via Online Search.: Joan Boyar, Kim S. Larsen, and Abyayananda Maiti.
In Joint International Conference on Frontiers in Algorithmics and Algorithmic Aspects in Information and Management (FAW-AAIM), volume 7285 of Lecture Notes in Computer Science, pages 303-314. Springer, 2012.
2011
[c27]
List Factoring and Relative Worst Order Analysis.: Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
In 8th Workshop on Approximation and Online Algorithms (WAOA), volume 6534 of Lecture Notes in Computer Science, pages 118-129. Springer, 2011.
2010
[j33]
A Theoretical Comparison of LRU and LRU-K.: Joan Boyar, Martin R. Ehmsen, Jens S. Kohrt, and Kim S. Larsen.
Acta Informatica, 47(7-8): 359-374, 2010.
[j32]
Competitive Analysis of the Online Inventory Problem.: Kim S. Larsen and Sanne Wøhlk.
European Journal of Operational Research, 207(2): 685-696, 2010.
[j31]
Priority Algorithms for Graph Optimization Problems.: Allan Borodin, Joan Boyar, Kim S. Larsen, and Nazanin Mirmohammadi.
Theoretical Computer Science, 411(1): 239-258, 2010.
[c26]
Better Bounds on Online Unit Clustering.: Martin R. Ehmsen and Kim S. Larsen.
In 12th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), volume 6139 of Lecture Notes in Computer Science, pages 371-382. Springer, 2010.
2009
[c25]
A Comparison of Performance Measures for Online Algorithms.: Joan Boyar, Sandy Irani, and Kim S. Larsen.
In 11th International Algorithms and Data Structures Symposium (WADS), volume 5664 of Lecture Notes in Computer Science, pages 119-130. Springer, 2009.
2007
[j30]
The Relative Worst Order Ratio Applied to Paging.: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
Journal of Computer and System Sciences, 73(5): 818-843, 2007.
2006
[j29]
The Maximum Resource Bin Packing Problem.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten M. Pedersen, and Sanne Wøhlk.
Theoretical Computer Science, 362(1-3):127-139, 2006.
[c24]
Theoretical Evidence for the Superiority of LRU-2 over LRU for the Paging Problem.: Joan Boyar, Martin R. Ehmsen, and Kim S. Larsen.
In 4th Workshop on Approximation and Online Algorithms (WAOA), volume 4368 of Lecture Notes in Computer Science, pages 95-107. Springer, 2006.
[c23]
Colour Reassignment in Tabu Search for the Graph Set T-Colouring Problem.: Marco Chiarandini, Thomas Stützle, and Kim S. Larsen.
In 3rd International Workshop on Hybrid Metaheuristics (HM), volume 4030 of Lecture Notes in Computer Science, pages 162-177. Springer, 2006.
2005
[j28]
Exponentially Decreasing Number of Operations in Balanced Trees.: Lars Jacobsen and Kim S. Larsen.
Acta Informatica, 82(4): 57-78, 2005.
[j27]
On-Line Seat Reservations via Off-Line Seating Arrangements.: Jens S. Kohrt and Kim S. Larsen.
International Journal of Foundations of Computer Science, 16(2): 381-397, 2005.
[c22]
The Maximum Resource Bin Packing Problem.: Joan Boyar, Leah Epstein, Lene M. Favrholdt, Jens S. Kohrt, Kim S. Larsen, Morten Monrad Pedersen, and Sanne Wøhlk.
In 15th International Symposium on Fundamentals of Computation Theory (FCT), volume 3623 of Lecture Notes in Computer Science, pages 397-408. Springer, 2005.
[c21]
The Relative Worst Order Ratio Applied to Paging.: Joan Boyar, Lene M. Favrholdt, and Kim S. Larsen.
In 16th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 718-727. ACM Press, 2005.
[c20]
Priority Algorithms for Graph Optimization Problems.: Allan Borodin, Joan Boyar, and Kim S. Larsen.
In 2nd Workshop on Approximation and Online Algorithms (WAOA), volume 3351 of Lecture Notes in Computer Science, pages 126-139. Springer, 2005.
[i2]
Balanced Binary Search Trees.: Arne Andersson, Rolf Fagerberg, and Kim S. Larsen.
In Dinesh P. Mehta and Sartaj Sahni, editors, Handbook of Data Structures and Applications, Chapman & Hall/CRC Computer & Information Science Series, pages 10-1-10-28. CRC Press, 2005.
2003
[j26]
Extending the Accommodating Function.: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Acta Informatica, 40(1): 3-35, 2003.
[j25]
Dynamic TCP Acknowledgment in the LogP Model.: Jens S. Frederiksen, Kim S. Larsen, John Noga, and Patchrawat Uthaisombut.
Journal of Algorithms, 48(2): 407-428, 2003.
[j24]
Relaxed Multi-Way Trees with Group Updates.: Kim S. Larsen.
Journal of Computer and System Sciences, 66(4): 657-670, 2003.
[j23]
Tight Bounds on the Competitive Ratio on Accommodating Sequences for the Seat Reservation Problem.: Eric Bach, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Tao Jiang, Kim S. Larsen, Guo-Hui Lin, and Rob van Stee.
Journal of Scheduling, 6(2):131-147, 2003.
[c19]
On-Line Seat Reservations via Off-Line Seating Arrangements.: Jens S. Frederiksen and Kim S. Larsen.
In 8th International Workshop on Algorithms and Data Structures (WADS), volume 2748 of Lecture Notes in Computer Science, pages 174-185. Springer, 2003.
2002
[j22]
On the Existence and Construction of Non-Extreme (a,b)-Trees.: Lars Jacobsen, Kim S. Larsen, and Morten N. Nielsen.
Information Processing Letters, 84(2): 69-73, 2002.
[j21]
Fair versus Unrestricted Bin Packing.: Yossi Azar, Joan Boyar, Leah Epstein, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Algorithmica, 34(2):181-196, 2002.
[j20]
Relaxed Red-Black Trees with Group Updates.: Kim S. Larsen.
Acta Informatica, 38(8): 565-586, 2002.
[c18]
Extending the Accommodating Function.: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
In 8th Annual International Computing and Combinatorics Conference (COCOON), volume 2387 of Lecture Notes in Computer Science, pages 87-96. Springer, 2002.
[c17]
Packet Bundling.: Jens S. Frederiksen and Kim S. Larsen.
In 8th Scandinavian Workshop on Algorithm Theory (SWAT), volume 2368 of Lecture Notes in Computer Science, pages 328-337. Springer, 2002.
2001
[j19]
The Competitive Ratio for On-Line Dual Bin Packing with Restricted Input Sequences.: Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
Nordic Journal of Computing, 8(4): 463-472, 2001.
[j18]
Relaxed Balance using Standard Rotations.: Kim S. Larsen, Eljas Soisalon-Soininen, and Peter Widmayer.
Algorithmica, 31(4): 501-512, 2001.
[j17]
Relaxed Balance for Search Trees with Local Rebalancing.: Kim S. Larsen, Thomas Ottmann, and Eljas Soisalon-Soininen.
Acta Informatica, 37(10): 743-763, 2001.
[j16]
Variants of (a,b)-Trees with Relaxed Balance.: Lars Jacobsen and Kim S. Larsen.
International Journal of Foundations of Computer Science, 12(4): 455-478, 2001.
[j15]
The Accommodating Function: a generalization of the competitive ratio.: Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
SIAM Journal on Computing, 31(1): 233-258, 2001.
[c16]
Exponentially Decreasing Number of Operations in Balanced Trees.: Lars Jacobsen and Kim S. Larsen.
In 7th Italian Conference on Theoretical Computer Science (ICTCS), volume 2202 of Lecture Notes in Computer Science, pages 293-311. Springer, 2001.
[c15]
Complexity of Layered Binary Search Trees with Relaxed Balance.: Lars Jacobsen and Kim S. Larsen.
In 7th Italian Conference on Theoretical Computer Science (ICTCS), volume 2202 of Lecture Notes in Computer Science, pages 269-284. Springer, 2001.
[c14]
Search Trees with Relaxed Balance and Near-Optimal Height.: Rolf Fagerberg, Rune E. Jensen, and Kim S. Larsen.
In 7th International Workshop on Algorithms and Data Structures (WADS), volume 2125 of Lecture Notes in Computer Science, pages 414-425. Springer, 2001.
[c13]
Relaxed Multi-Way Trees with Group Updates.: Kim S. Larsen.
In 20th ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems (PODS), pages 93-101. ACM Press, 2001.
[i1] Dictionary of Computer Science, Engineering, and Technology.: Philip A. Laplante, editor.
CRC Press, 2001. One of 58 contributors.
2000
[j14]
AVL Trees with Relaxed Balance.: Kim S. Larsen.
Journal of Computer and System Sciences, 61(3): 508-522, 2000.
[c12]
Better Bounds on the Accommodating Ratio for the Seat Reservation Problem.: Eric Bach, Joan Boyar, Tao Jiang, Kim S. Larsen, and Guo-Hui Lin.
In 6th Annual International Computing and Combinatorics Conference (COCOON), volume 1858 of Lecture Notes in Computer Science, pages 221-231. Springer, 2000.
[c11]
Fair versus Unrestricted Bin Packing.: Yossi Azar, Joan Boyar, Lene M. Favrholdt, Kim S. Larsen, and Morten N. Nielsen.
In 7th Scandinavian Workshop on Algorithm Theory (SWAT), volume 1851 of Lecture Notes in Computer Science, pages 200-213. Springer, 2000.
1999
[j13]
On Grouping in Relational Algebra.: Kim S. Larsen.
International Journal of Foundations of Computer Science, 10(3): 301-311, 1999.
[j12]
The Seat Reservation Problem.: Joan Boyar and Kim S. Larsen.
Algorithmica, 25(4): 403-417, 1999.
[j11]
Partially Persistent Binary Search Trees with Transcript Operations.: Kim S. Larsen.
Discrete Mathematics and Theoretical Computer Science, 3(3): 95-107, 1999.
[c10]
The Accommodating Function: a generalization of the competitive ratio.: Joan Boyar, Kim S. Larsen, and Morten N. Nielsen.
In 6th International Workshop on Algorithms and Data Structures (WADS), volume 1663 of Lecture Notes in Computer Science, pages 74-79. Springer, 1999.
1998
[j10]
Sort Order Problems in Relational Databases.: Kim S. Larsen.
International Journal of Foundations of Computer Science, 9(4): 399-429, 1998.
[j9]
Amortized Constant Relaxed Rebalancing using Standard Rotations.: Kim S. Larsen.
Acta Informatica, 35(10): 859-874, 1998.
[j8]
Parametric Permutation Routing via Matchings.: Peter Høyer and Kim S. Larsen.
Nordic Journal of Computing, 5(2):105-114, 1998.
[j7]
Regular Expressions with Nested Levels of Back Referencing Form a Hierarchy.: Kim S. Larsen.
Information Processing Letters, 65(4):169-172, 1998.
[c9]
Partially Persistent Binary Search Trees with Transcript Operations.: Kim S. Larsen.
In 15th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1373 of Lecture Notes in Computer Science, pages 350-363. Springer, 1998.
1997
[j6]
Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.: Joan Boyar, Rolf Fagerberg, and Kim S. Larsen.
Journal of Computer and System Sciences, 55(3): 504-521, 1997.
[c8]
Relaxed Balance for Search Trees with Local Rebalancing.: Kim S. Larsen, Thomas Ottmann, and Eljas Soisalon-Soininen.
In 5th Annual European Symposium on Algorithms (ESA), volume 1284 of Lecture Notes in Computer Science, pages 350-363. Springer, 1997.
[c7]
Relaxed Balance through Standard Rotations.: Kim S. Larsen, Eljas Soisalon-Soininen, and Peter Widmayer.
In 5th International Workshop on Algorithms and Data Structures (WADS), volume 1272 of Lecture Notes in Computer Science, pages 450-461. Springer, 1997.
1996
[j5]
Efficient Rebalancing of B-Trees with Relaxed Balance.: Kim S. Larsen and Rolf Fagerberg.
International Journal of Foundations of Computer Science, 7(2):169-186, 1996.
1995
[c6]
Efficient Simplification of Bisimulation Formulas.: Uffe Engberg and Kim S. Larsen.
In 1st International Workshop on Tools and Algorithms for the Construction and Analysis of Systems (TACAS), volume 1019 of Lecture Notes in Computer Science, pages 111-132. Springer, 1995.
[c5]
Amortization Results for Chromatic Search Trees, with an Application to Priority Queues.: Joan Boyar, Rolf Fagerberg, and Kim S. Larsen.
In 4th International Workshop on Algorithms and Data Structures (WADS), volume 955 of Lecture Notes in Computer Science, pages 270-281. Springer, 1995.
[c4]
B-Trees with Relaxed Balance.: Kim S. Larsen and Rolf Fagerberg.
In 9th International Parallel Processing Symposium (IPPS), pages 196-202. IEEE Computer Society Press, 1995.
1994
[j4]
Efficient Rebalancing of Chromatic Search Trees.: Joan F. Boyar and Kim S. Larsen.
Journal of Computer and System Sciences, 49(3): 667-682, 1994.
[j3]
Injectivity of Composite Functions.: Kim S. Larsen and Michael I. Schwartzbach.
Journal of Symbolic Computation, 17(5): 393-408, 1994.
[j2]
Bounds on Certain Multiplications of Affine Combinations.: Joan Boyar, Faith Fich, and Kim S. Larsen.
Discrete Applied Mathematics, 52(2):155-167, 1994.
[c3]
AVL Trees with Relaxed Balance.: Kim S. Larsen.
In 8th International Parallel Processing Symposium (IPPS), pages 888-893. IEEE Computer Society Press, 1994.
1992
[j1]
A New Formalism for Relational Algebra.: Kim S. Larsen, Michael I. Schwartzbach, and Erik M. Schmidt.
Information Processing Letters, 41(3):163-168, 1992.
[c2]
Efficient Rebalancing of Chromatic Search Trees.: Joan F. Boyar and Kim S. Larsen.
In 3rd Scandinavian Workshop on Algorithm Theory (SWAT), volume 621 of Lecture Notes in Computer Science, pages 151-164. Springer, 1992.
1989
[c1]
Fully Abstract Models for a Process Language with Refinement.: Mogens Nielsen, Uffe Engberg, and Kim S. Larsen.
In REX: Linear Time, Branching Time and Partial Order in Logics and Models of Concurrency (REX), volume 354 of Lecture Notes in Computer Science, pages 523-548. Springer, 1989.