Publications

C. Ortlieb and J. M. Schmidt. Toward Grünbaum's Conjecture. In Proceedings of the 19th Scandinavian Symposium on Algorithm Theory (SWAT'24), to appear.

O.-H. S. Lo and J. M. Schmidt. Generalized Cut Trees for Edge-Connectivity. Journal of Combinatorial Theory, Series B, to appear.

T. Böhme, J. Harant, M. Kriesell, S. Mohr and J. M. Schmidt. Rooted Minors and Locally Spanning Subgraphs. Journal of Graph Theory, 105(2):209-229, 2024.
DOI

C. Ortlieb. Schnyder woods and long induced paths in 3-connected planar graphs. In Proceedings of 16th Latin American Theoretical Informatics Symposium (LATIN'24), pages 19-30, 2024.
DOI   PDF

M. Kriesell, T. L. Chan and J. M. Schmidt. Contractible edges in longest cycles. Journal of Graph Theory, 103(3):542-563, 2023.
DOI   PDF

V. B. Le and C. Rosenke. Computing Optimal Leaf Roots of Chordal Cographs in Linear Time. In Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT'23), pages 348-362, 2023.
DOI

U. S. Danda, G. Ramakrishna, J. M. Schmidt and M. Srikanth. On short fastest paths in temporal graphs. In Proceedings of the 15th International Conference and Workshops on Algorithms and Computation (WALCOM'21), pages 40-51, 2021.
DOI   PDF

I. Fabrici, J. Harant, S. Mohr and J. M. Schmidt. Circumference of essentially 4-connected planar triangulations. Journal of Graph Algorithms and Applications, 25(1):121-132, 2021.
DOI   PDF

O.-H. S. Lo, J. M. Schmidt and M. Thorup. Compact cactus representations of all non-trivial min-cuts. Discrete Applied Mathematics, 303:296-304, 2021.
DOI   PDF

O.-H. S. Lo and J. M. Schmidt. Cycle spectra of contraction-critically 4-connected planar graphs. Graphs and Combinatorics, 37(6):2129-2137, 2021.
DOI   PDF

I. Fabrici, J. Harant, S. Mohr and J. M. Schmidt. Longer cycles in essentially 4-connected planar graphs. Discussiones Mathematicae Graph Theory, 40:269-277, 2020.
DOI   Talk   PDF

I. Fabrici, J. Harant, S. Mohr and J. M. Schmidt. On the circumference of essentially 4-connected planar graphs. Journal of Graph Algorithms and Applications, 24(1):21-46, 2020.
DOI   PDF

O.-H. S. Lo, J. M. Schmidt, N. Van Cleemput and C. T. Zamfirescu. Shortness coefficient of cyclically 4-edge-connected cubic graphs. Electronic Journal of Combinatorics, 27(1):P1.43, 1-14, 2020.
DOI   PDF

J. E. Preißer and J. M. Schmidt. Computing vertex-disjoint paths in large graphs using MAOs. Algorithmica, 82(1):146-162, 2020.
DOI   PDF

C. Rosenke and M. Liskiewicz. The generic combinatorial algorithm for image matching with classes of projective transformations. Information and Computation, 275:104550, 2020.
DOI

C. Rosenke and R. Tredup. The complexity of synthesizing elementary net systems relative to natural parameters. Journal of Computer and System Sciences, 110:37-54, 2020.
DOI

T. Liebke and C. Rosenke. Faster Enabledness-Updates for the Reachability Graph Computation. In Proceedings of International Workshop on Petri Nets and Software Engineering (PNSE@Petri Nets'20), pages 108-117, 2020.
PDF

L. Schlipf and J. M. Schmidt. Edge-orders. Algorithmica, 81(5):1881-1900, 2019.
DOI   PDF

L. Schlipf and J. M. Schmidt. Simple computation of st-edge- and st-numberings from ear decompositions. Information Processing Letters, 145:58-63, 2019.
DOI   PDF

R. Tredup and C. Rosenke. On the Hardness of Synthesizing Boolean Nets. In Proceedings of the International Workshop on Algorithms & Theories for the Analysis of Event Data 2019 (ATAED@Petri Nets/ACSD'19), pages 71-86, 2019.
PDF

R. Tredup and C. Rosenke. The Complexity of Synthesis for 43 Boolean Petri Net Types. In Proceedings of the International Conference on Theory and Applications of Models of Computation (TAMC'19), pages 615-634, 2019.
DOI

M. Kriesell and J. M. Schmidt. More on foxes. Journal of Graph Theory, 89(2):101-114, 2018.
DOI   PDF

O.-H. S. Lo and J. M. Schmidt. Longest cycles in cyclically 4-edge-connected cubic planar graphs. Australasian Journal of Combinatorics, 72(1):155-162, 2018.
URL   PDF

O.-H. S. Lo and J. M. Schmidt. A cut tree representation for pendant pairs. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), pages 38:1-38:9, 2018.
DOI   PDF

M. Mnich, I. Rutter and J. M. Schmidt. Linear-time recognition of map graphs with outerplanar witness. Discrete Optimization, 28:63-77, 2018.
DOI   PDF

J. E. Preißer and J. M. Schmidt. Computing vertex-disjoint paths in large graphs using MAOs. In Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC'18), pages 13:1-13:12, 2018.
DOI   PDF

A. Schmid and J. M. Schmidt. Computing 2-walks in polynomial time. ACM Transactions on Algorithms, 14(2):22.1-22.18, 2018.
DOI   PDF

A. Schmid and J. M. Schmidt. Computing Tutte paths. In Proceedings of the 45th International Colloquium on Automata, Languages and Programming (ICALP'18), pages 98:1-98:14, 2018.
DOI   PDF

J. M. Schmidt. Tight bounds for the vertices of degree k in minimally k-connected graphs. Journal of Graph Theory, 88(1):146-153, 2018.
DOI   PDF

R. Tredup, C. Rosenke and K. Wolf. Elementary Net Synthesis Remains NP-Complete Even for Extremely Simple Inputs. In Proceedings of the International Conference on Application and Theory of Petri Nets and Concurrency (Petri Nets'18), pages 40-59, 2018.
DOI

R. Tredup and C. Rosenke. Narrowing down the Hardness Barrier of Synthesizing Elementary Net Systems.  In Proceedings of the 29th International Conference on Concurrency Theory (CONCUR'18), 118:16:1-16:15, 2018.
DOI

K. Mehlhorn, A. Neumann and J. M. Schmidt. Certifying 3-edge-connectivity. Algorithmica, 77(2):309-335, 2017.
DOI   PDF

L. Schlipf and J. M. Schmidt. Edge-orders. In Proceedings of the 44th International Colloquium on Automata, Languages and Programming (ICALP'17), pages 75:1-75:14, 2017.
DOI   PDF

A. Adamaszek, M. Adamaszek, M. Mnich and J. M. Schmidt. Lower bounds for locally highly connected graphs. Graphs and Combinatorics, 32(5):1641-1650, 2016.
DOI   PDF

H. Alt, M. S. Payne, J. M. Schmidt and D. R. Wood. Thoughts on Barnette's conjecture. The Australasian Journal of Combinatorics, 64(2):354-365, 2016.
URL   PDF

M. Mnich, I. Rutter and J. M. Schmidt. Linear-time recognition of map graphs with outerplanar witness. In Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'16), pages 5:1-5:14, 2016.
DOI   PDF

J. M. Schmidt. Mondshein sequences (a.k.a. (2,1)-orders). SIAM Journal on Computing, 45(6):1985-2003, 2016.
DOI   Talk   PDF

R. Nevries and C. Rosenke. Towards a Characterization of Leaf Powers by Clique Arrangements. Graphs and Combinatorics, 32(5):2053-2077, 2016.
DOI

C. Rosenke. The exact complexity of projective image matching. Journal of Computer and System Sciences, 82(8):1360-1387, 2016.
DOI

T. Biedl and J. M. Schmidt. Small-area orthogonal drawings of 3-connected graphs. In Proceedings of the 23rd International Symposium on Graph Drawing (GD'15), pages 153-165, 2015.
DOI   PDF

T. Miltzow, J. M. Schmidt and M. Xia. Counting K_4-subdivisions. Discrete Mathematics, 338(12):2387-2392, 2015.
DOI   PDF

A. Schmid and J. M. Schmidt. Computing 2-walks in polynomial time. In Proceedings of the 32nd Symposium on Theoretical Aspects of Computer Science (STACS'15), pages 676-688, 2015.
DOI  PDF

J. M. Schmidt and P. Valtr. Cubic plane graphs on a given point set. Computational Geometry, 48:1-13, 2015.
DOI   PDF

R. Nevries and C. Rosenke. Characterizing and computing the structure of clique intersections in strongly chordal graphs. Discrete Applied Mathematics, 181:221-234, 2015.
DOI

C. Doerr, G. Ramakrishna and J. M. Schmidt. Computing minimum cycle bases in weighted partial 2-trees in linear time. Journal of Graph Algorithms and Applications, 18(3):325-346, 2014.
DOI   PDF

M. S. Payne, J. M. Schmidt and D. R. Wood. Which point sets admit a k-angulation? Journal of Computational Geometry, 5(1):41-55, 2014.
DOI   PDF

J. M. Schmidt. The Mondshein sequence. In Proceedings of the 41st International Colloquium on Automata, Languages and Programming (ICALP'14), pages 967-978, 2014.
DOI   Talk   PDF

C. Rosenke and D. Waltemath. How Can Semantic Annotations Support the Identification of Network Similarities? In Proceedings of the 7th International Workshop on Semantic Web Applications and Tools for Life Sciences (SWAT4LS'14), 2014.
PDF

C. Doerr, G. Ramakrishna and J. M. Schmidt. Computing minimum cycle bases in weighted partial 2-trees in linear time. In 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), pages 225-236, 2013.
DOI   Talk   PDF

A. Elmasry, K. Mehlhorn and J. M. Schmidt. Every DFS tree of a 3-connected graph contains a contractible edge. Journal of Graph Theory, 72(1):112-121, 2013.
DOI   PDF

K. Mehlhorn, A. Neumann and J. M. Schmidt. Certifying 3-edge-connectivity. In 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG'13), pages 358-369, 2013.
DOI   PDF

J. M. Schmidt. Contractions, removals and certifying 3-connectivity in linear time. SIAM Journal on Computing, 42(2):494-535, 2013.
DOI   PDF

J. M. Schmidt. A simple test on 2-vertex- and 2-edge-connectivity. Information Processing Letters, 113(7):241-244, 2013.
DOI   PDF

J. M. Schmidt. A planarity test via construction sequences. In 38th International Symposium on Mathematical Foundations of Computer Science (MFCS'13), pages 765-776, 2013.
DOI   PDF

C. Hundt. On the computational complexity of projective image matching. Ph.D. Thesis. Universität zu Lübeck, Germany, 2012.
PDF

A. Elmasry, K. Mehlhorn and J. M. Schmidt. An O(n+m) certifying triconnnectivity algorithm for Hamiltonian graphs. Algorithmica, 62(3):754-766, 2012.
DOI   PDF

C. Knauer, L. Schlipf, J. M. Schmidt and H. R. Tiwary. Largest inscribed rectangles in convex polygons. Journal of Discrete Algorithms, 13:78-85, 2012.
DOI   PDF

J. M. Schmidt. Construction sequences and certifying 3-connectivity. Algorithmica, 62:192-208, 2012.
DOI   Talk   PDF

J. M. Schmidt and P. Valtr. Cubic plane graphs on a given point set. In Proceedings of the 28th Annual Symposium on Computational Geometry (SoCG'12), pages 201-208, 2012.
DOI   Talk   PDF

J. M. Schmidt. Certifying 3-connectivity in linear time. In Proceedings of the 39th International Colloquium on Automata, Languages and Programming (ICALP'12), pages 786-797, 2012.
DOI   PDF

C. Hundt and F. Wendland. Efficient Two-Dimensional Pattern Matching with Scaling and Rotation and Higher-Order Interpolation. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM'12), pages 124-137, 2012.
DOI

J. M. Schmidt. Structure and constructions of 3-connected graphs. Ph.D. Thesis. Freie Universität Berlin, Germany, 2011.
URL   PDF

C. Hundt and M. Liskiewicz. New complexity bounds for image matching under rotation and scaling. Journal of Discrete Algorithms, 9(1):122-136, 2011.
DOI

J. M. Schmidt. Construction sequences and certifying 3-connectedness. In Proceedings of the 27th Symposium on Theoretical Aspects of Computer Science (STACS'10), pages 633-644, 2010.
DOI   Talk   PDF

A. Brandstädt, C. Hundt, F. Mancini and P. Wagner. Rooted directed path graphs are leaf powers. Discrete Mathematics, 310(4):897-910, 2010.
DOI

C. Hundt. Affine Image Matching Is Uniform TC⁰-Complete. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM'10), pages 13-25, 2010.
DOI

A. Brandstädt, C. Hundt and R. Nevries. Efficient Edge Domination on Hole-Free Graphs in Polynomial Time. In Proceedings of the Latin American Symposium on Theoretical Informatics (LATIN'10), pages 650-661, 2010.
DOI

J. M. Schmidt. Interval stabbing problems in small integer ranges. In Proceedings of the 20th International Symposium on Algorithms and Computation (ISAAC'09), pages 163-172, 2009.
DOI   Talk   SourceCode   PDF

C. Hundt, M. Liskiewicz and R. Nevries. A combinatorial geometrical approach to two-dimensional robust pattern matching with scaling and rotation. Theoretical Computer Science, 410(51):5317-5333, 2009.
DOI

C. Hundt and M. Liskiewicz. New Complexity Bounds for Image Matching under Rotation and Scaling. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM'09), pages 127-141, 2009.
DOI

H. Fan, C. Hundt and Y. L. Wu and J. Ernst. Algorithms and Implementation for Interconnection Graph Problem. In Proceedings of the International Conference on Combinatorial Optimization and Applications (COCOA'08), pages 201-210, 2008.
DOI

C. Hundt and U. Ochsenfahrt. Damaged BZip Files Are Difficult to Repair. In Proceedings of the International Computing and Combinatorics Conference (COCOON'08), pages 12-21, 2008.
DOI

C. Hundt and M. Liskiewicz. Two-Dimensional Pattern Matching with Combined Scaling and Rotation. In Proceedings of the Annual Symposium on Combinatorial Pattern Matching (CPM'08), pages 5-17, 2008.
DOI

A. Brandstädt and C. Hundt. Ptolemaic Graphs and Interval Graphs Are Leaf Powers. In Proceedings of the Latin American Symposium on Theoretical Informatics (LATIN'08), pages 479-491, 2008.
DOI

C. Hundt and M. Liskiewicz. Combinatorial Bounds and Algorithmic Aspects of Image Matching under Projective Transformations. In Proceedings of the International Symposium on Mathematical Foundations of Computer Science (MFCS'08), pages 395-406, 2008.
DOI

M. Chimani, P. Mutzel and J. M. Schmidt. Efficient extraction of multiple Kuratowski subdivisions. In Proceedings of the 15th International Symposium on Graph Drawing (GD'07), pages 159-170, 2007.
DOI   Talk   PDF

J. M. Schmidt. Effiziente Extraktion von Kuratowski-Teilgraphen. Diploma Thesis. Technische Universität Dortmund, Germany, 2007.
Talk   PDF

C. Hundt and M. Liskiewicz. On the Complexity of Affine Image Matching. In Proceedings of the Annual Symposium on Theoretical Aspects of Computer Science (STACS'07), pages 284-295, 2007.
DOI

C. Hundt and M. Liskiewicz. A Combinatorial Geometric Approach to Linear Image Matching. In Proceedings of the Electronic Colloquium on Computational Complexity, 2007.
PDF

B. Baranski, T. Bartz-Beielstein, R. Ehlers, T. Kajendran, B. Kosslers, J. Mehnen, T. Polazek, R. Reimholz, J. M. Schmidt, K. Schmitt, D. Seis, R. Slodzinski, S. Steeg, N. Wiemann and M. Zimmermann. The impact of group reputation in multiagent environments. In Proceedings of the IEEE Congress on Evolutionary Computation (CEC'06), pages 1224-1231, 2006.
DOI   PDF

B. Baranski, T. Bartz-Beielstein, R. Ehlers, T. Kajendran, B. Kosslers, J. Mehnen, T. Polazek, R. Reimholz, J. M. Schmidt, K. Schmitt, D. Seis, R. Slodzinski, S. Steeg, N. Wiemann and M. Zimmermann. High-order punishment and the evolution of cooperation. In Proceedings of the Genetic and Evolutionary Computation Conference (GECCO'06), pages 379-380, 2006.
DOI   PDF

C. Hundt, M. Liskiewicz and U. Wölfel. Provably Secure Steganography and the Complexity of Sampling. In Proceedings of the International Symposium on Algorithms and Computation (ISAAC'06), pages 754-763, 2006.
DOI

C. Hundt. Width-Bounded Query Languages. Diploma Thesis. Universität Rostock, Germany, 2005.