Prof. Dr. Tobias Friedrich

All Publications in 2021

The following listing contains all publications of the current members of the Algorithm Engineering group in 2021.

Conference Publications


  • Selfish Creation of Socia... - Download
    Bilò, Davide; Friedrich, Tobias; Lenzner, Pascal; Lowski, Stefanie; Melnichenko, Anna Selfish Creation of Social NetworksConference on Artificial Intelligence (AAAI) 2021
  • Aziz, Haris; Cseh, Agnes; Dickerson, John; McElfresh, Duncan Optimal Kidney Exchange with ImmunosuppressantsConference on Artificial Intelligence (AAAI) 2021
  • Aziz, Haris; Chan, Hau; Cseh, Ágnes; Li, Bo; Ramezani, Fahimeh; Wang, Chenhao Multi-Robot Task Allocation—Complexity and ApproximationAutonomous Agents and Multiagent Systems (AAMAS) 2021
  • Kraiczy, Sonja; Cseh, Ágnes; Manlove, David On Weakly and Strongly Popular RankingsAutonomous Agents and Multiagent Systems (AAMAS) 2021
  • Cooley, Madison; Greene, Casey; Issac, Davis; Pividori, Milton; Sullivan, Blair Parameterized Algorithms for Identifying Gene Co-Expression Modules via Weighted Clique DecompositionApplied and Computational Discrete Algorithms (ACDA) 2021
  • Adaptive Sampling for Fas... - Download
    Quinzan, Francesco; Doskoč, Vanja; Göbel, Andreas; Friedrich, Tobias Adaptive Sampling for Fast Constrained Maximization of Submodular FunctionsArtificial Intelligence and Statistics (AISTATS) 2021: 964–972
  • Connected k-Partition of ... - Download
    Borndörfer, Ralf; Casel, Katrin; Issac, Davis; Niklanovits, Aikaterini; Schwartz, Stephan; Zeif, Ziena Connected k-Partition of k-Connected Graphs and c-Claw-Free GraphsApproximation Algorithms for Combinatorial Optimization Problems (APPROX) 2021
  • Learning Languages with D... - Download
    Berger, Julian; Böther, Maximilian; Doskoč, Vanja; Gadea Harder, Jonathan; Klodt, Nicolas; Kötzing, Timo; Lötzsch, Winfried; Peters, Jannik; Schiller, Leon; Seifert, Lars; Wells, Armin; Wietheger, Simon Learning Languages with Decidable HypothesesComputability in Europe (CiE) 2021
  • Learning Languages in the... - Download
    Kötzing, Timo; Seidel, Karen Learning Languages in the Limit from Positive Information with Finitely Many Memory ChangesComputability in Europe (CiE) 2021
  • Towards a Map for Increme... - Download
    Khazraei, Ardalan; Kötzing, Timo; Seidel, Karen Towards a Map for Incremental Learning in the Limit from Positive and Negative InformationComputability in Europe (CiE) 2021
  • Mapping Monotonic Restric... - Download
    Doskoč, Vanja; Kötzing, Timo Mapping Monotonic Restrictions in Inductive InferenceComputability in Europe (CiE) 2021
  • Normal Forms for Semantic... - Download
    Doskoč, Vanja; Kötzing, Timo Normal Forms for Semantically Witness-Based Learners in Inductive InferenceComputability in Europe (CiE) 2021
  • Bläsius, Thomas; Tobias, Friedrich; Christopher, Weyand Efficiently Computing Maximum Flows in Scale-Free NetworksEuropean Symposium on Algorithms (ESA) 2021
  • Near-Optimal Deterministi... - Download
    Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Near-Optimal Deterministic Single-Source Distance Sensitivity OraclesEuropean Symposium on Algorithms (ESA) 2021: 18:1–18:17
  • Efficiently Approximating... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian Efficiently Approximating Vertex Cover on Scale-Free Networks with Underlying Hyperbolic GeometryEuropean Symposium on Algorithms (ESA) 2021: 20:1–20:15
  • Balanced Crown Decomposit... - Download
    Casel, Katrin; Friedrich, Tobias; Issac, Davis; Niklanovits, Aikaterini; Zeif, Ziena Balanced Crown Decomposition for Connectivity ConstraintsEuropean Symposium on Algorithms (ESA) 2021: 26:1–26:15
  • From Symmetry to Asymmetr... - Download
    Behrendt, Lukas; Casel, Katrin; Friedrich, Tobias; Lagodzinski, J. A. Gregor; Löser, Alexander; Wilhelm, Marcus From Symmetry to Asymmetry: Generalizing {TSP} Approximations by ParametrizationFundamentals of Computation Theory (FCT) 2021: 53–66
  • Fine-Grained Localization... - Download
    Berger, Julian; Bleidt, Tibor; Büßemeyer, Martin; Ding, Marcus; Feldmann, Moritz; Feuerpfeil, Moritz; Jacoby, Janusch; Schröter, Valentin; Sievers, Bjarne; Spranger, Moritz; Stadlinger, Simon; Wullenweber, Paul; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Fine-Grained Localization, Classification and Segmentation of Lungs with Various DiseasesCVPR Workshop on Fine-Grained Visual Categorization (FGVC@CVPR) 2021
  • Lower Bounds from Fitness... - Download
    Doerr, Benjamin; Kötzing, Timo Lower Bounds from Fitness Levels Made EasyGenetic and Evolutionary Computation Conference (GECCO) 2021
  • Evolutionary Minimization... - Download
    Böther, Maximilian; Schiller, Leon; Fischbeck, Philipp; Molitor, Louise; Krejca, Martin S.; Friedrich, Tobias Evolutionary Minimization of Traffic CongestionGenetic and Evolutionary Computation Conference (GECCO) 2021: 937–945
    Best Paper Award (RWA Track)
  • A spectral independence v... - Download
    Friedrich, Tobias; Göbel, Andreas; Krejca, Martin; Pappik, Marcus A spectral independence view on hard spheres via block dynamicsInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 66:1–66:15
  • On Counting (Quantum-)Gra... - Download
    Lagodzinski, J. A. Gregor; Göbel, Andreas; Casel, Katrin; Friedrich, Tobias On Counting (Quantum-)Graph Homomorphisms in Finite Fields of Prime OrderInternational Colloquium on Automata, Languages and Programming (ICALP) 2021: 91:1–91:15
  • Fine-Grained Complexity o... - Download
    Casel, Katrin; Schmid, Markus L. Fine-Grained Complexity of Regular Path QueriesInternational Conference on Database Theory (ICDT) 2021
  • Two-Stage Facility Locati... - Download
    Krogmann, Simon; Lenzner, Pascal; Molitor, Louise; Skopalik, Alexander Two-Stage Facility Location Games with Strategic Clients and FacilitiesInternational Joint Conference on Artificial Intelligence (IJCAI) 2021
  • Antoniadis, Antonios; Kumar, Gunjan; Kumar, Nikhil Skeletons and Minimum Energy SchedulingInternational Symposium on Algorithms and Computation (ISAAC) 2021
  • The Impact of Geometry on... - Download
    Bläsius, Thomas; Friedrich, Tobias; Krejca, Martin; Molitor, Louise The Impact of Geometry on Monochrome Regions in the Flip Schelling ProcessInternational Symposium on Algorithms and Computation (ISAAC) 2021
  • Casel, Katrin; Friedrich, Tobias; Issac, Davis; Klodt, Nicolas; Seifert, Lars; Zahn, Arthur A Color-blind 3-Approximation for Chromatic Correlation Clustering and Improved HeuristicsKnowledge Discovery and Data Mining (KDD) 2021: 882–891
  • Space-Efficient Fault-Tol... - Download
    Bilò, Davide; Cohen, Sarel; Friedrich, Tobias; Schirneck, Martin Space-Efficient Fault-Tolerant Diameter OraclesMathematical Foundations of Computer Science (MFCS) 2021: 18:1–18:16
  • Drug Repurposing for Mult... - Download
    Kißig, Otto; Taraz, Martin; Cohen, Sarel; Doskoč, Vanja; Friedrich, Tobias Drug Repurposing for Multiple COVID Strains using Collaborative FilteringICLR Workshop on Machine Learning for Preventing and Combating Pandemics (MLPCP@ICLR) 2021
  • Solving Non-Uniform Plant... - Download
    Friedrich, Tobias; Neumann, Frank; Rothenberger, Ralf; Sutton, Andrew M. Solving Non-Uniform Planted and Filtered Random SAT Formulas GreedilyTheory and Applications of Satisfiability Testing (SAT) 2021: 188–206
  • Force-Directed Embedding ... - Download
    Bläsius, Thomas; Friedrich, Tobias; Katzmann, Maximilian Force-Directed Embedding of Scale-Free Networks in the Hyperbolic PlaneSymposium on Experimental Algorithms (SEA) 2021: 22:1–22:18
  • The Impact of Heterogenei... - Download
    Bläsius, Thomas; Friedrich, Tobias; Göbel, Andreas; Levy, Jordi; Rothenberger, Ralf The Impact of Heterogeneity and Geometry on the Proof Complexity of Random SatisfiabilitySymposium on Discrete Algorithms (SODA) 2021: 42–53
  • Efficiency and Stability ... - Download
    Friedemann, Wilhelm; Friedrich, Tobias; Gawendowicz, Hans; Lenzner, Pascal; Melnichenko, Anna; Peters, Jannik; Stephan, Daniel; Vaichenker, Michael Efficiency and Stability in Euclidean Network DesignSymposium on Parallelism in Algorithms and Architectures (SPAA) 2021: 232–242
  • Kißig, Otto; Taraz, Martin; Cohen, Sarel; Friedrich, Tobias Drug Repurposing Using Link Prediction on Knowledge GraphsICML Workshop on Computational Biology (WCB@ICML) 2021

Journal Publications


  • Pairwise Preferences in t... - Download
    Cseh, Ágnes; Juhos, Attila Pairwise Preferences in the Stable Marriage ProblemACM Transactions on Economics and Computation (TEAC) 2021: 1–28
  • Cseh, Ágnes; Kavitha, Telikepalli Popular matchings in complete graphsAlgorithmica 2021: 1–31
  • Organizing time exchanges... - Download
    Andersson, Tommy; Cseh, Ágnes; Ehlers, Lars; Erlanson, Albin Organizing time exchanges: Lessons from matching marketsAmerican Economic Journal: Microeconomics 2021: 338–73
  • A Simplified Run Time Ana... - Download
    Doerr, Benjamin; Krejca, Martin S. A Simplified Run Time Analysis of the Univariate Marginal Distribution Algorithm on LeadingOnesTheoretical Computer Science 2021: 121–128
  • On the Complexity of the ... - Download
    Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L. On the Complexity of the Smallest Grammar Problem over Fixed AlphabetsTheory of Computing Systems 2021: 344–409
  • The Complexity of Depende... - Download
    Bläsius, Thomas; Friedrich, Tobias; Schirneck, Martin The Complexity of Dependency Detection and Discovery in Relational DatabasesCoRR 2021
    ArXiv preprint