Publications

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

2017

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).
(orig)
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)
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)
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)
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)
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)
On Kernelization and Approximation for the Vector Connectivity Problem
Kratsch, S., Sorge, M. Algorithmica. 79, 96–138 (2017).
(pdf) (orig)

2016

The Minimum Shared Edges Problem on Planar Graphs
Fluschnik, T., Sorge, M. arXiv:1602.01385. (2016).
(pdf)
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)
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)
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)
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)
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)
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)

2015

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

2014

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)
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)
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)
Exploiting a Hypergraph Model for Finding Golomb Rulers
Sorge, M., Moser, H., Niedermeier, R., Weller, M. Acta Informatica. 51, 449–471 (2014).
(pdf) (orig)
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)

2013

A More Complicated Hardness Proof for Finding Densest Subgraphs in Bounded Degree Graphs
Sorge, M. arXiv:1306.6698. (2013).
(pdf)
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)
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)
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)

2012

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

2011

On Making Directed Graphs Eulerian
Sorge, M. Diplomarbeit, Institut für Informatik, Friedrich-Schiller-Universität Jena, Germany. (2011).
(pdf)
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)
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)

2010

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

2009

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)