Publications

See also my dblp and Google Scholar profiles or download my complete bibtex file.

Book chapter

  1. Complexity of Arc Routing Problems
    Bevern, R. van, Niedermeier, R., Sorge, M., Weller, M. In: Arc Routing: Problems, Methods, and Applications. pp. 19–52. SIAM (2014).
    (pdf) (orig)

Journal and conference articles

  1. Optimal Discretization is Fixed-parameter Tractable
    Kratsch, S., Masarı́k Tomás, Muzi, I., Pilipczuk, M., Sorge, M. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA ’21). SIAM (2021).
    (pdf)

  2. Efficient fully dynamic elimination forests with applications to detecting long paths and cycles
    Chen, J., Czerwinski, W., Disser, Y., Feldmann, A.E., Hermelin, D., Nadara, W., Pilipczuk, M., Pilipczuk, M., Sorge, M., Wróblewski, B., Zych-Pawlewicz, A. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA ’21). SIAM (2021).
    (pdf)

  3. The Complexity of Connectivity Problems in Forbidden-Transition Graphs and Edge-Colored Graphs
    Bellitto, T., Li, S., Okrasa, K., Pilipczuk, M., Sorge, M. In: Proceedings of the 31st International Symposium on Algorithms and Computation (ISAAC ’20). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2020).
    (pdf)

  4. A Double Exponential Lower Bound for the Distinct Vectors Problem
    Pilipczuk, M., Sorge, M. Discrete Mathematics & Theoretical Computer Science. 22, 1–4 (2020).
    (pdf) (orig)

  5. Threshold Treewidth and Hypertree Width
    Ganian, R., Schidler, A., Sorge, M., Szeider, S. In: Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence, IJCAI 2020. pp. 1898–1904. AAAI Press (2020).
    (orig)

  6. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
    Kanj, I.A., Komusiewicz, C., Sorge, M., Leeuwen, E.J. van. SIAM Journal on Discrete Mathematics. 34, 640–681 (2020).
    (pdf) (orig)

  7. Efficient Algorithms for Measuring the Funnel-Likeness of DAGs
    Millani, M.G., Molter, H., Niedermeier, R., Sorge, M. Journal of Combinatorial Optimization. 39, 216–245 (2020).
    (pdf) (orig)

  8. On Computing Centroids According to the p-Norms of Hamming Distance Vectors
    Chen, J., Hermelin, D., Sorge, M. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA ’19). pp. 28:1–28:16. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2019).
    (pdf) (orig)

  9. Packing directed circuits quarter-integrally
    Masařík, T., Muzi, I., Pilipczuk, M., Rzążewski, P., Sorge, M. In: Proceedings of the 27th Annual European Symposium on Algorithms (ESA ’19). pp. 72:1–72:13 (2019).
    (pdf) (orig)

  10. Matchings under Preferences: Strength of Stability and Trade-offs
    Chen, J., Skowron, P., Sorge, M. In: Proceedings of the 20th ACM Conference on Economics and Computation (EC ’19). pp. 41–59. ACM (2019).
    (pdf) (orig)

  11. Your Rugby Mates Don’t Need to Know your Colleagues: Triadic Closure with Edge Colors
    Bulteau, L., Grüttemeier, N., Komusiewicz, C., Sorge, M. In: Proceedings of the 11th International Conference on Algorithms and Complexity (CIAC ’19). pp. 99–111. Springer (2019).
    (pdf) (orig)

  12. The Complexity of Routing with Collision Avoidance
    Fluschnik, T., Morik, M., Sorge, M. Journal of Computer and System Sciences. 102, 69–86 (2019).
    (pdf) (orig)

  13. The Parameterized Complexity of the Minimum Shared Edges Problem
    Fluschnik, T., Kratsch, S., Niedermeier, R., Sorge, M. Journal of Computer and System Sciences. 106, 23–46 (2019).
    (pdf) (orig)

  14. Assessing the Computational Complexity of Multi-Layer Subgraph Detection
    Bredereck, R., Komusiewicz, C., Kratsch, S., Molter, H., Niedermeier, R., Sorge, M. Network Science. 7, 215–241 (2019).
    (pdf) (orig)

  15. The Minimum Feasible Tileset problem
    Disser, Y., Kratsch, S., Sorge, M. Algorithmica. 81, 1126–1151 (2019).
    (pdf) (orig)

  16. Computational Complexity Aspects of Point Visibility Graphs
    Himmel, A.-S., Hoffmann, C., Kunz, P., Froese, V., Sorge, M. Discrete Applied Mathematics. 254, 283–290 (2019).
    (pdf) (orig)

  17. The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
    Bevern, R. van, Fluschnik, T., Mertzios, G.B., Molter, H., Sorge, M., Suchý, O. Discrete Optimization. 30, 20–50 (2018).
    (pdf) (orig)

  18. Cluster Editing in Multi-Layer and Temporal Graphs
    Chen, J., Suchý, O., Molter, H., Sorge, M. In: Proceedings of the 29th International Symposium on Algorithms and Computation (ISAAC ’18). pp. 24:1–24:13. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018).
    (pdf) (orig)

  19. Matching algorithms for assigning orthologs after genome duplication events
    Fertin, G., Hüffner, F., Komusiewicz, C., Sorge, M. Computational Biology and Chemistry. 74, 379–390 (2018).
    (orig)

  20. Solving Partition Problems Almost Always Requires Pushing Many Vertices Around
    Kanj, I.A., Komusiewicz, C., Sorge, M., Leeuwen, E.J. van. In: Proceedings of the 26th Annual European Symposium on Algorithms (ESA ’18). pp. 51:1–51:14. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018).
    (pdf) (orig)

  21. How Hard Is It to Satisfy (Almost) All Roommates?
    Chen, J., Hermelin, D., Sorge, M., Yedidsion, H. In: Proceedings of the 45th International Colloquium on Automata, Languages, and Programming (ICALP ’18). pp. 35:1–35:15. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2018).
    (pdf) (orig)

  22. Efficient Algorithms for Measuring the Funnel-Likeness of DAGs
    Millani, M.G., Molter, H., Niedermeier, R., Sorge, M. In: Proceedings of the 5th International Symposium on Combinatorial Optimization (ISCO ’18). pp. 183–195. Springer (2018).
    (pdf) (orig)

  23. The Parameterized Complexity of Centrality Improvement in Networks
    Hoffmann, C., Molter, H., Sorge, M. In: Proceedings of the 44th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM ’18). pp. 111–124. Springer (2018).
    (pdf) (orig)

  24. Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
    Kanj, I.A., Komusiewicz, C., Sorge, M., Leeuwen, E.J. van. Journal of Computer and System Sciences. 92, 22–47 (2018).
    (pdf) (orig)

  25. A parameterized approximation algorithm for the mixed and windy capacitated arc routing problem: Theory and experiments
    Bevern, R. van, Komusiewicz, C., Sorge, M. Networks. 70, 262–278 (2017).
    (pdf) (orig)

  26. The Complexity of Routing with Few Collisions
    Fluschnik, T., Morik, M., Sorge, M. In: Proceedings of the 21st International Symposium on Fundamentals of Computation Theory (FCT ’17). pp. 257–270. Springer (2017).
    (pdf) (orig)

  27. Adapting the Bron-Kerbosch algorithm for enumerating maximal cliques in temporal graphs
    Himmel, A.-S., Molter, H., Niedermeier, R., Sorge, M. Social Network Analysis and Mining. 7, 35:1–35:16 (2017).
    (pdf) (orig)

  28. Finding Secluded Places of Special Interest in Graphs
    Bevern, R. van, Fluschnik, T., Mertzios, G.B., Molter, H., Sorge, M., Suchý, O. In: Proceedings of the 11th International Symposium on Parameterized and Exact Computation (IPEC ’16). pp. 5:1–5:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017).
    (pdf) (orig)

  29. Assessing the Computational Complexity of Multi-Layer Subgraph Detection
    Bredereck, R., Komusiewicz, C., Kratsch, S., Molter, H., Niedermeier, R., Sorge, M. In: Proceedings of the 10th International Conference on Algorithms and Complexity (CIAC ’17). pp. 128–139. Springer (2017).
    (pdf) (orig)

  30. On Kernelization and Approximation for the Vector Connectivity Problem
    Kratsch, S., Sorge, M. Algorithmica. 79, 96–138 (2017).
    (pdf) (orig)

  31. Exploiting hidden structure in selecting dimensions that distinguish vectors
    Froese, V., Bevern, R. van, Niedermeier, R., Sorge, M. Journal of Computer and System Sciences. 82, 521–535 (2016).
    (pdf) (orig)

  32. H-index manipulation by merging articles: Models, theory, and experiments
    Bevern, R. van, Komusiewicz, C., Niedermeier, R., Sorge, M., Walsh, T. Artificial Intelligence. 240, 19–35 (2016).
    (pdf) (orig)

  33. Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs
    Kanj, I.A., Komusiewicz, C., Sorge, M., Leeuwen, E.J. van. In: Proceedings of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT ’16). pp. 14:1–14:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2016).
    (pdf) (orig)

  34. Twins in Subdivision Drawings of Hypergraphs
    Bevern, R. van, Kanj, I.A., Komusiewicz, C., Niedermeier, R., Sorge, M. In: Proceedings of the 24th International Symposium on Graph Drawing & Network Visualization (GD ’16). pp. 67–80. Springer (2016).
    (pdf) (orig)

  35. H-Index Manipulation by Undoing Merges
    Bevern, R. van, Molter, H., Komusiewicz, C., Niedermeier, R., Sorge, M., Walsh, T. In: Proceedings of the 22nd European Conference on Artificial Intelligence (ECAI ’16). pp. 895–903. IOS Press (2016).
    (pdf) (orig)

  36. Enumerating maximal cliques in temporal graphs
    Himmel, A.-S., Molter, H., Niedermeier, R., Sorge, M. In: Proceedings of the 2016 IEEE/ACM International Conference on Advances in Social Networks Analysis and Mining, (ASONAM ’16). pp. 337–344. IEEE Computer Society (2016).
    (pdf) (orig)

  37. The Parameterized Complexity of the Minimum Shared Edges Problem
    Fluschnik, T., Kratsch, S., Niedermeier, R., Sorge, M. In: Proceedings of the 35th IARCS Annual Conference on Foundation of Software Technology and Theoretical Computer Science (FSTTCS ’15). pp. 448–462. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2015).
    (pdf) (orig)

  38. Approximation Algorithms for Mixed, Windy, and Capacitated Arc Routing Problems
    Bevern, R. van, Komusiewicz, C., Sorge, M. In: Proceedings of the 15th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems (ATMOS ’15). pp. 130–143. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015).
    (pdf) (orig)

  39. H-Index Manipulation by Merging Articles: Models, Theory, and Experiments
    Bevern, R. van, Komusiewicz, C., Niedermeier, R., Sorge, M., Walsh, T. In: Proceedings of the 24th International Joint Conference on Artificial Intelligence (IJCAI ’15). pp. 808–814. AAAI Press (2015).
    (pdf) (orig)

  40. Finding Highly Connected Subgraphs
    Hüffner, F., Komusiewicz, C., Sorge, M. In: Proceedings of the 41st International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM ’15). pp. 254–265. Springer (2015).
    (pdf) (orig)

  41. Finding Connected Subgraphs of Fixed Minimum Density: Implementation and Experiments
    Komusiewicz, C., Sorge, M., Stahl, K. In: Proceedings of the 14th International Symposium on Experimental Algorithms (SEA ’15). pp. 82–93. Springer (2015).
    (pdf) (orig)

  42. On Kernelization and Approximation for the Vector Connectivity Problem
    Kratsch, S., Sorge, M. In: Proceedings of the 10th International Symposium on Parameterized and Exact Computation (IPEC ’15). pp. 377–388. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik (2015).
    (pdf) (orig)

  43. Polynomial-Time Data Reduction for the Subset Interconnection Design Problem
    Chen, J., Komusiewicz, C., Niedermeier, R., Sorge, M., Suchý, O., Weller, M. SIAM Journal on Discrete Mathematics. 29, 1–25 (2015).
    (pdf) (orig)

  44. An Algorithmic Framework for Fixed-Cardinality Optimization in Sparse Graphs Applied to Dense Subgraph Problems
    Komusiewicz, C., Sorge, M. Discrete Applied Mathematics. 193, 145–161 (2015).
    (pdf) (orig)

  45. The Minimum Feasible Tileset problem
    Disser, Y., Kratsch, S., Sorge, M. In: Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA ’14). pp. 144–155. Springer (2014).
    (pdf) (orig)

  46. On the Parameterized Complexity of Computing Balanced Partitions in Graphs
    Bevern, R. van, Feldmann, A.E., Sorge, M., Suchý, O. Theory of Computing Systems. 57, 1–35 (2014).
    (pdf) (orig)

  47. Constant-factor approximations for Capacitated Arc Routing without triangle inequality
    Bevern, R. van, Hartung, S., Nichterlein, A., Sorge, M. Operations Research Letters. 4, 290–292 (2014).
    (pdf) (orig)

  48. Exploiting a Hypergraph Model for Finding Golomb Rulers
    Sorge, M., Moser, H., Niedermeier, R., Weller, M. Acta Informatica. 51, 449–471 (2014).
    (pdf) (orig)

  49. On the Parameterized Complexity of Computing Graph Bisections
    Bevern, R. van, Feldmann, A.E., Sorge, M., Suchý, O. In: Proceedings of the 39th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’13). pp. 76–88. Springer (2013).
    (pdf) (orig)

  50. Effective and Efficient Data Reduction for the Subset Interconnection Design Problem
    Chen, J., Komusiewicz, C., Niedermeier, R., Sorge, M., Suchý, O., Weller, M. In: Proceedings of the 24th International Symposium on Algorithms and Computation (ISAAC ’13). pp. 361–371 (2013).
    (pdf) (orig)

  51. A Parameterized Complexity Analysis of Combinatorial Feature Selection Problems
    Froese, V., Bevern, R. van, Niedermeier, R., Sorge, M. In: Proceedings of the 38th International Symposium on Mathematical Foundations of Computer Science (MFCS ’13). pp. 445–456. Springer (2013).
    (pdf) (orig)

  52. Exploiting a Hypergraph Model for Finding Golomb Rulers
    Sorge, M., Moser, H., Niedermeier, R., Weller, M. In: Proceedings of the 2nd International Symposium on Combinatorial Optimization (ISCO ’12). pp. 368–379. Springer (2012).
    (pdf) (orig)

  53. Finding Dense Subgraphs of Sparse Graphs
    Komusiewicz, C., Sorge, M. In: Proceedings of the 7th International Symposium on Parameterized and Exact Computation (IPEC ’12). pp. 242–251. Springer (2012).
    (pdf) (orig)

  54. Exact combinatorial algorithms and experiments for finding maximum k-plexes
    Moser, H., Niedermeier, R., Sorge, M. Journal of Combinatorial Optimization. 24, 347–373 (2012).
    (pdf) (orig)

  55. A New View on Rural Postman Based on Eulerian Extension and Matching
    Sorge, M., Bevern, R. van, Niedermeier, R., Weller, M. Journal of Discrete Algorithms. 16, 12–33 (2012).
    (pdf) (orig)

  56. A New View on Rural Postman Based on Eulerian Extension and Matching
    Sorge, M., Bevern, R. van, Niedermeier, R., Weller, M. In: Proceedings of the 22nd International Workshop on Combinatorial Algorithms (IWOCA ’11). pp. 310–323. Springer (2011).
    (pdf) (orig)

  57. From Few Components to an Eulerian Graph by Adding Arcs
    Sorge, M., Bevern, R. van, Niedermeier, R., Weller, M. In: Proceedings of the 37th International Workshop on Graph-Theoretic Concepts in Computer Science (WG ’11). pp. 307–318. Springer (2011).
    (pdf) (orig)

  58. Algorithms and Experiments for Clique Relaxations—Finding Maximum s-Plexes
    Moser, H., Niedermeier, R., Sorge, M. In: Proceedings of the 8th International Symposium on Experimental Algorithms (SEA ’09). pp. 233–244. Springer (2009).
    (pdf) (orig)

Theses

  1. Be Sparse! Be Dense! Be Robust! Elements of Parameterized Algorithmics
    Sorge, M. Doktorarbeit, Institut für Softwaretechnik und Theoretische Informatik, Technische Universität Berlin, Germany. (2017).
    (pdf)

  2. On Making Directed Graphs Eulerian
    Sorge, M. Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany. (2011).
    (pdf)

  3. Algorithmic Aspects of Golomb Ruler Construction
    Sorge, M. Studienarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany. (2010).
    (pdf)