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. SIAM (2014).
    (pdf) (orig)

Journal Articles

  1. The Minimum Feasible Tileset problem
    Disser, Y., Kratsch, S., Sorge, M. Algorithmica. (2018).
    (pdf)

  2. 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. (2018).
    (pdf)

  3. Computational Complexity Aspects of Point Visibility Graphs
    Himmel, A.-S., Hoffmann, C., Kunz, P., Froese, V., Sorge, M. Discrete Applied Mathematics. (2018).
    (pdf)

  4. 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)

  5. 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)

  6. 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)

  7. 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)

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

  9. 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)

  10. 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)

  11. 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)

  12. 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)

  13. 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)

  14. 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)

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

  16. 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)

  17. 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)

Conference Articles

  1. 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) (2018).
    (pdf)

  2. 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)

  3. 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)

  4. 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)

  5. 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)

  6. 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)

  7. 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)

  8. 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)

  9. 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)

  10. 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). Springer (2016).
    (pdf) (orig)

  11. 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)

  12. 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)

  13. 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)

  14. 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)

  15. 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)

  16. 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)

  17. 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)

  18. 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)

  19. 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)

  20. 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)

  21. 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)

  22. 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)

  23. 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)

  24. 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)

  25. 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)

  26. 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)

  27. 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)