Publications - Current Year

Article

M. Abdulaziz and K. Mehlhorn

“A Formal Correctness Proof of Edmonds’ Blossom Shrinking Algorithm,” Journal of Automated Reasoning, vol. 70, no. 2, 2026.

mehr

BibTeX

@article{Abdulaziz26,
TITLE = {A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm},
AUTHOR = {Abdulaziz, Mohammad and Mehlhorn, Kurt},
LANGUAGE = {eng},
ISSN = {0168-7433},
DOI = {10.1007/s10817-026-09747-y},
PUBLISHER = {D. Reidel Pub. Co.},
ADDRESS = {Dordrecht, Holland},
YEAR = {2026},
DATE = {2026},
JOURNAL = {Journal of Automated Reasoning},
VOLUME = {70},
NUMBER = {2},
EID = {s10817-026-09747-y},
}

Endnote

%0 Journal Article
%A Abdulaziz, Mohammad
%A Mehlhorn, Kurt 
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T A Formal Correctness Proof of Edmonds' Blossom Shrinking Algorithm : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0012-A6D1-4
%R 10.1007/s10817-026-09747-y
%7 2026-02-16
%D 2026
%J Journal of Automated Reasoning
%V 70
%N 2
%Z sequence number: s10817-026-09747-y
%I D. Reidel Pub. Co.
%C Dordrecht, Holland
%@ false

Article

R. Becker, D. Cenzato, S.-H. Kim, T. Kociumaka, B. Kodric, A. Policriti, and N. Prezza

“On the Complexity of Computing the Co-lexicographic Width of a Regular Language,” Journal of Computer and System Sciences, vol. 158, 2026.

mehr

BibTeX

@article{Becker26,
TITLE = {On the Complexity of Computing the Co-lexicographic Width of a Regular Language},
AUTHOR = {Becker, Ruben and Cenzato, Davide and Kim, Sung-Hwan and Kociumaka, Tomasz and Kodric, Bojana and Policriti, Alberto and Prezza, Nicola},
LANGUAGE = {eng},
ISSN = {0022-0000},
DOI = {10.1016/j.jcss.2026.103759},
PUBLISHER = {Elsevier},
ADDRESS = {Amsterdam},
YEAR = {2026},
DATE = {2026},
JOURNAL = {Journal of Computer and System Sciences},
VOLUME = {158},
EID = {103759},
}

Endnote

%0 Journal Article
%A Becker, Ruben
%A Cenzato, Davide
%A Kim, Sung-Hwan
%A Kociumaka, Tomasz
%A Kodric, Bojana
%A Policriti, Alberto
%A Prezza, Nicola
%+ External Organizations
External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
%T On the Complexity of Computing the Co-lexicographic Width of a Regular
  Language : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0010-6B67-3
%R 10.1016/j.jcss.2026.103759
%7 2026-01-23
%D 2026
%J Journal of Computer and System Sciences
%V 158
%Z sequence number: 103759
%I Elsevier
%C Amsterdam
%@ false

Conference paper

R. Duan, X. Mao, X. Shu, and L. Yin

“A Faster Directed Single-Source Shortest Path Algorithm,” in 53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026), London, UK.

mehr

Abstract

This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].

BibTeX

@inproceedings{Duan_ICALP26,
TITLE = {A Faster Directed Single-Source Shortest Path Algorithm},
AUTHOR = {Duan, Ran and Mao, Xiao and Shu, Xinkai and Yin, Longhui},
URL = {https://arxiv.org/abs/2602.07868},
EPRINT = {2602.07868},
EPRINTTYPE = {arXiv},
PUBLISHER = {Schloss Dagstuhl},
YEAR = {2026},
PUBLREMARK = {Accepted},
ABSTRACT = {This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].},
BOOKTITLE = {53rd International Colloquium on Automata, Languages, and Programming (ICALP 2026)},
SERIES = {Leibniz International Proceedings in Informatics},
ADDRESS = {London, UK},
}

Endnote

%0 Conference Proceedings
%A Duan, Ran
%A Mao, Xiao
%A Shu, Xinkai 
%A Yin, Longhui
%+ External Organizations
External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T A Faster Directed Single-Source Shortest Path Algorithm : 
%U http://hdl.handle.net/21.11116/0000-0012-F6E3-6
%U https://arxiv.org/abs/2602.07868
%D 2026
%B 53rd EATCS International Colloquium on Automata, Languages, and Programming
%Z date of event: 2026-07-07 - 2026-07-10
%C London, UK
%X This paper presents a new deterministic algorithm for single-source shortest paths (SSSP) on real non-negative edge-weighted directed graphs, with running time $O(m\sqrt{\log n}+\sqrt{mn\log n\log \log n})$, which is $O(m\sqrt{\log n\log \log n})$ for sparse graphs. This improves the recent breakthrough result of $O(m\log^{2/3} n)$ time for directed SSSP algorithm [Duan, Mao, Mao, Shu, Yin 2025].
%K Computer Science, Data Structures and Algorithms, cs.DS
%B 53rd International Colloquium on Automata, Languages, and Programming 
%I Schloss Dagstuhl
%B Leibniz International Proceedings in Informatics

Article

A. Duyster and T. Kociumaka

“Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts,” Theory of Computing Systems, vol. 70, 2026.

mehr

BibTeX

@article{Duyster26,
TITLE = {Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts},
AUTHOR = {Duyster, Anouk and Kociumaka, Tomasz},
LANGUAGE = {eng},
ISSN = {1432-4350},
DOI = {10.1007/s00224-026-10266-x},
PUBLISHER = {Springer},
ADDRESS = {New York, NY},
YEAR = {2026},
DATE = {2026},
JOURNAL = {Theory of Computing Systems},
VOLUME = {70},
EID = {11},
}

Endnote

%0 Journal Article
%A Duyster, Anouk 
%A Kociumaka, Tomasz 
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Logarithmic-Time Internal Pattern Matching Queries in Compressed and Dynamic Texts : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0012-AD83-5
%R 10.1007/s00224-026-10266-x
%7 2026-02-23
%D 2026
%J Theory of Computing Systems
%V 70
%Z sequence number: 11
%I Springer
%C New York, NY
%@ false

Conference paper

Y. Jiang, D. Nanongkai, and P. Sawettamalya

“Minimum s--t Cuts with Fewer Cut Queries,” in Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026), Vancouver, Canada, 2026.

mehr

BibTeX

@inproceedings{JiangSODA26,
TITLE = {Minimum $s$--$t$ Cuts with Fewer Cut Queries},
AUTHOR = {Jiang, Yonggang and Nanongkai, Danupon and Sawettamalya, Pachara},
LANGUAGE = {eng},
ISBN = {978-1-61197-897-1},
DOI = {10.1137/1.9781611978971.12},
PUBLISHER = {SIAM},
YEAR = {2026},
DATE = {2026},
BOOKTITLE = {Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2026)},
PAGES = {258--296},
ADDRESS = {Vancouver, Canada},
}

Endnote

%0 Conference Proceedings
%A Jiang, Yonggang
%A Nanongkai, Danupon
%A Sawettamalya, Pachara
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
%T Minimum s--t Cuts with Fewer Cut Queries : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0012-0683-1
%R 10.1137/1.9781611978971.12
%D 2026
%B Thirty-Seventh Annual ACM-SIAM Symposium on Disrete Algorithms
%Z date of event: 2026-01-11 - 2026-01-14
%C Vancouver, Canada
%B Proceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms 
%P 258 - 296
%I SIAM
%@ 978-1-61197-897-1

Article

A. Karrenbauer, K. Mehlhorn, P. Misra, P. L. Rinaldi, A. Twelsiek, A. Haqi, and S. R. Shateranloo

“Improving Order with Queues,” Journal of Combinatorial Optimization, vol. 51, no. 3, 2026.

mehr

BibTeX

@article{Karrenbauer26,
TITLE = {Improving Order with Queues},
AUTHOR = {Karrenbauer, Andreas and Mehlhorn, Kurt and Misra, Pranabendu and Rinaldi, Paolo Luigi and Twelsiek, Anna and Haqi, Alireza and Shateranloo, Siavash Rahimi},
LANGUAGE = {eng},
ISSN = {1382-6905},
DOI = {10.1007/s10878-026-01419-2},
PUBLISHER = {Springer},
ADDRESS = {New York, NY},
YEAR = {2026},
DATE = {2026},
JOURNAL = {Journal of Combinatorial Optimization},
VOLUME = {51},
NUMBER = {3},
EID = {39},
}

Endnote

%0 Journal Article
%A Karrenbauer, Andreas 
%A Mehlhorn, Kurt 
%A Misra, Pranabendu
%A Rinaldi, Paolo Luigi
%A Twelsiek, Anna
%A Haqi, Alireza
%A Shateranloo, Siavash Rahimi
%+ Algorithms and Complexity, MPI for Informatics, Max Planck Society
Algorithms and Complexity, MPI for Informatics, Max Planck Society
External Organizations
External Organizations
External Organizations
External Organizations
External Organizations
%T Improving Order with Queues : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0012-FBB4-6
%R 10.1007/s10878-026-01419-2
%7 2026-04-26
%D 2026
%J Journal of Combinatorial Optimization
%V 51
%N 3
%Z sequence number: 39
%I Springer
%C New York, NY
%@ false

Article

F. Lobyrev and P. Emeliyanenko

“Linear Growth Patterns and Growth Parameter Dynamics in Northern Pike (Esox lucius) Populations From Non-Flowing Water Bodies Across Their Natural Range,” Fisheries Management and Ecology, 2026.

mehr

BibTeX

@article{Lobyrev26,
TITLE = {Linear Growth Patterns and Growth Parameter Dynamics in Northern Pike ({E}sox&#8201;lucius) Populations From Non-Flowing Water Bodies Across Their Natural Range},
AUTHOR = {Lobyrev, Feodor and Emeliyanenko, Pavel},
LANGUAGE = {eng},
DOI = {10.1111/fme.70055},
PUBLISHER = {Wiley},
YEAR = {2026},
JOURNAL = {Fisheries Management and Ecology},
}

Endnote

%0 Journal Article
%A Lobyrev, Feodor
%A Emeliyanenko, Pavel
%+ External Organizations
Algorithms and Complexity, MPI for Informatics, Max Planck Society
%T Linear Growth Patterns and Growth Parameter Dynamics in Northern Pike (Esox&#8201;lucius) Populations From Non-Flowing Water Bodies Across Their Natural Range : 
%G eng
%U http://hdl.handle.net/21.11116/0000-0012-9FFA-0
%R 10.1111/fme.70055
%7 2026-02-06
%D 2026
%8 06.02.2026
%J Fisheries Management and Ecology
%I Wiley