2024W

• Algorithmic Geometry / 192.133 / VU
• Algorithms in Graph Theory / 192.018 / VU
• Randomized Algorithms / 192.045 / VU
• Seminar in Algorithms Graphs and Geometry / 186.862 / SE

• The Complexity of Cluster Vertex Splitting and Company / Firbas, A., Dobler, A., Holzer, F., Schafellner, J., Sorge, M., Villedieu, A., & Wißmann, M. (2024). The Complexity of Cluster Vertex Splitting and Company. In SOFSEM 2024: Theory and Practice of Computer Science (pp. 226–239).
• Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation / Hatzel, M., Jaffke, L., LIMA BARBOSA, C. P., Masařík, T., Pilipczuk, M., Sharma, R., & Sorge, M. (2023). Fixed-parameter tractability of DIRECTED MULTICUT with three terminal pairs parameterized by the size of the cutset: twin-width meets flow-augmentation. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA23) (pp. 3229–3244). https://doi.org/10.1137/1.9781611977554.ch123
• Planarizing Graphs and Their Drawings by Vertex Splitting / Nöllenburg, M., Sorge, M., Terziadis, S., Villedieu, A., Wu, H.-Y., & Wulms, J. (2023). Planarizing Graphs and Their Drawings by Vertex Splitting. In P. Angelini & R. von Haxleden (Eds.), Graph Drawing and Network Visualization. GD 2022 (pp. 232–246). Springer. https://doi.org/10.1007/978-3-031-22203-0_17
• The Influence of Dimensions on the Complexity of Computing Decision Trees / Kobourov, S. G., Löffler, M., Montecchiani, F., Pilipczuk, M., Rutter, I., Seidel, R., Sorge, M., & Wulms, J. (2023). The Influence of Dimensions on the Complexity of Computing Decision Trees. In B. Williams, Y. Chen, & J. Neville (Eds.), Proceedings of the 37th AAAI Conference on Artificial Intelligence (pp. 8343–8350). AAAI Press. https://doi.org/10.1609/aaai.v37i7.26006
• On Computing Optimal Tree Ensembles / Komusiewicz, C., Kunz, P., Sommer, F., & Sorge, M. (2023). On Computing Optimal Tree Ensembles. In A. Krause, E. Brunskill, K. Cho, B. Engelhardt, S. Sabato, & J. Scarlett (Eds.), Proceedings of the 40th International Conference on Machine Learning (pp. 17364–17374). http://hdl.handle.net/20.500.12708/192688
• Game Implementation: What Are the Obstructions? / Chen, J., Layegh Khavidaki, S. N., Haydn, S. V., Simola, S., & Sorge, M. (2023). Game Implementation: What Are the Obstructions? In Proceedings of the 37th AAAI Conference on Artificial Intelligence (pp. 5557–5564). AAAI Press. https://doi.org/10.34726/5365
  Download: PDF (178 KB)
• Turbocharging Heuristics for Weak Coloring Numbers / Dobler, A., Sorge, M., & Villedieu, A. (2022). Turbocharging Heuristics for Weak Coloring Numbers. In S. Chechik, G. Navarro, E. Rotenberg, & G. Herman (Eds.), 30th Annual European Symposium on Algorithms (ESA 2022) (pp. 1–18). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.ESA.2022.44
  Download: PDF (1.01 MB)
  Projects: HumAlgo (2018–2023) / REVEAL-AI (2020–2024)
• Threshold Treewidth and Hypertree Width / Ganian, R., Schidler, A., Sorge, M., & Szeider, S. (2022). Threshold Treewidth and Hypertree Width. Journal of Artificial Intelligence Research, 74, 1687–1713. https://doi.org/10.1613/JAIR.1.13661
  Download: PDF (6.1 MB)
  Projects: NFPC (2018–2022) / Parameterisierte Analyse in der Künstlichen Intelligenz (2021–2026) / REVEAL-AI (2020–2024) / SLIM (2019–2024)
• Constant Congestion Brambles in Directed Graphs / Masařík, T., Pilipczuk, M., Rzążewski, P., & Sorge, M. (2022). Constant Congestion Brambles in Directed Graphs. SIAM Journal on Discrete Mathematics, 36(2), 922–938. https://doi.org/10.1137/21M1417661
  Download: Unauthorized reproduction of this article is prohibited. (1.2 MB)
• Constant Congestion Brambles / Hatzel, M., Pilipczuk, M., Komosa, P., & Sorge, M. (2022). Constant Congestion Brambles. Discrete Mathematics & Theoretical Computer Science, 24(1), Article 6. https://doi.org/10.46298/dmtcs.6699
  Download: PDF (570 KB)
• Planarizing Graphs and their Drawings by Vertex Splitting / Nickel, S., Nöllenburg, M., Sorge, M., Villedieu, A., Wu, H.-Y., & Wulms, J. (2022). Planarizing Graphs and their Drawings by Vertex Splitting. arXiv. https://doi.org/10.34726/3828
  Download: PDF (1.91 MB)
  Projects: Engineering Linear Ordering Algorithms for Optimizing Data Visualizations (2020–2025) / HumAlgo (2018–2023)
• Computational aspects of multiwinner approval voting via p-norm Hamming distance vectors / Chen, J., Hermelin, D., & Sorge, M. (2021). Computational aspects of multiwinner approval voting via p-norm Hamming distance vectors. Aggregation across disciplines: connections and frameworks, Paris, France. http://hdl.handle.net/20.500.12708/87316
• On (Coalitional) Exchange-Stable Matching / Chen, J., Chmurovic, A., Jogl, F., & Sorge, M. (2021). On (Coalitional) Exchange-Stable Matching. In Algorithmic Game Theory (pp. 205–220). LNCS / Springer. https://doi.org/10.1007/978-3-030-85947-3_14
• Cluster Editing Parameterized Above Modification-Disjoint P3-Packings / Li, S., Pilipczuk, M., & Sorge, M. (2021). Cluster Editing Parameterized Above Modification-Disjoint P3-Packings. In 38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) (pp. 1–16). LIPICS. https://doi.org/10.4230/LIPIcs.STACS.2021.49
• Threshold Treewidth and Hypertree Width / Ganian, R., Schidler, A., Sorge, M., & Szeider, S. (2021). Threshold Treewidth and Hypertree Width. In Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence. IJCAI’20: Twenty-Ninth International Joint Conference on Artificial Intelligence, Yokohama, Japan. https://doi.org/10.24963/ijcai.2020/263
• Optimal Discretization is Fixed-parameter Tractable / Kratsch, S., Masařík, T., Muzi, I., Pilipczuk, M., & Sorge, M. (2021). Optimal Discretization is Fixed-parameter Tractable. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 1702–1719). ACM. https://doi.org/10.1137/1.9781611976465.103
• 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. (2021). Efficient fully dynamic elimination forests with applications to detecting long paths and cycles. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA) (pp. 796–809). Siam. https://doi.org/10.1137/1.9781611976465.50
• Matchings under Preferences: Strength of Stability and Tradeoffs / Chen, J., Skowron, P., & Sorge, M. (2021). Matchings under Preferences: Strength of Stability and Tradeoffs. ACM Transactions on Economics and Computation, 9(4), 1–55. https://doi.org/10.1145/3485000
• Fractional Matchings under Preferences: Stability and Optimality / Chen, J., Roy, S., & Sorge, M. (2021). Fractional Matchings under Preferences: Stability and Optimality. In Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence. IJCAI 2021 - 30th International Joint Conference on Artificial Intelligence, Montreal, Canada, Canada. https://doi.org/10.24963/ijcai.2021/13
• Your rugby mates don't need to know your colleagues: Triadic closure with edgecolors / Bulteau, L., Grüttemeier, N., Komusiewicz, C., & Sorge, M. (2021). Your rugby mates don’t need to know your colleagues: Triadic closure with edgecolors. Journal of Computer and System Sciences, 120, 75–96. https://doi.org/10.1016/j.jcss.2021.03.001

• Establishing hereditary graph properties via vertex splitting / Firbas, A. (2023). Establishing hereditary graph properties via vertex splitting [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2023.103864
  Download: PDF (1.96 MB)
• Turbocharging heuristics for weak coloring numbers / Dobler, A. (2021). Turbocharging heuristics for weak coloring numbers [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2021.91580
  Download: PDF (4.86 MB)