Detailseite
Projekt Druckansicht

GRK 1408:  Methoden für diskrete Strukturen

Fachliche Zuordnung Mathematik
Förderung Förderung von 2006 bis 2015
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 20088418
 
Erstellungsjahr 2016

Zusammenfassung der Projektergebnisse

Die Diskrete Mathematik hat sich in den vergangenen Jahrzehnten als eigenständige Disziplin im Überschneidungsbereich von Mathematik und Informatik etabliert. Ihre Werkzeuge, Modelle, Methoden und Algorithmen leisten wesentliche Beiträge zu wichtigen Anwendungsgebieten wie Logistik, Telekommunikation, Verkehrsplanung, Computergraphik und Bildverarbeitung sowie zu Gen-Sequenzierung und anderen Fragestellungen der Bio-Informatik. Moderne Methoden der Diskreten Mathematik zeichnen sich durch eine große Vielfalt, Flexibilität und Spannbreite aus: Das Spektrum umfasst algorithmische, probabilistische, geometrische, topologische, algebraische und optimierungstheoretische Methoden. Die Kombination und das Zusammenspiel dieser Methoden hat in den vergangenen Jahren die Durchschlagskraft und den Anwendungsbereich kombinatorischer Argumente erheblich erweitert, insbesondere bei Anwendungen in der Informatik, in der Optimierung und im Operations Research. Im Rahmen des Graduiertenkollegs haben die starken und eng vernetzten Arbeitsgruppen der beteiligten Wissenschaftlerinnen und Wissenschaftler substanzielle Beiträge zur aktuellen Forschung hinsichtlich der genannten Aspekte der Diskreten Mathematik geleistet. Im Rahmen der Promotionsausbildung haben die Stipendiatinnen und Stipendiaten die aktuellen Hilfsmittel und Methoden aus verschiedenen Richtungen und Teilgebieten der Mathematik und Informatik kennengelernt, den erfolgreichen Einsatz, die Kombination und Integration solcher Methoden geübt und dabei aktiv an der mathematischen Forschung teilgenommen. Die Promotionszeit im Graduiertenkolleg hat ihnen also breitere Übersicht verschafft und sie mit einem vielfältigeren Werkzeugkasten ausgestattet, als dies in einer einzelnen Arbeitsgruppe möglich gewesen wäre. Das Graduiertenkolleg war in all seinen Komponenten international aufgestellt, und zwar im Hinblick auf die Gruppe der Stipendiatinnen und Stipendiaten, die Zusammenarbeit mit vielen ausländischen Fachkolleginnen und Fachkollegen, das Gäste- und Vortragsprogramm des Kollegs, das Kursangebot (auf Englisch) als auch die Studien- und Konferenzangebote, die den Stipendiatinnen und Stipendiaten erschlossen und nahegelegt wurden. Im Rahmen des neunjährigen Förderzeitraums des Graduiertenkollegs (plus ein Jahr Auslauffinanzierung) wurden 39 Stipendiatinnen und Stipendiaten gefördert, die fast alle innerhalb der dreijährigen Förderung ihre Dissertation erfolgreich fertiggestellt haben. Darüber hinaus wurden fünf Postdoktorand/innen gefördert. Zahlreiche Absolvent/innen haben inzwischen erfolgreich eine eigene wissenschaftliche Karriere gestartet und repräsentieren eindrucksvoll den großen Erfolg des Graduiertenkollegs.

Projektbezogene Publikationen (Auswahl)

  • Diametral pairs of linear extensions
    Graham Brightwell and Mareike Massow
  • Grid intersection graphs and order dimension
    Steven Chaplick, Stefan Felsner, Udo Hoffmann, and Veit Wiechert
  • Linear extension diameter of downset lattices of 2-dimensional posets
    Stefan Felsner and Mareike Massow
  • On the dimension of posets with cover graphs of treewidth
    Gwenaël Joret, Piotr Micek, William T. Trotter, Ruidong Wang, and Veit Wiechert
  • Topological minors of cover graphs and dimension
    Piotr Micek and Veit Wiechert
  • Domino-Pflasterungen und Aztekensterne. Mathematische Semesterberichte, 53(1):81–99, 2006
    Felix Breuer and Daria Schymura
  • sharpSAT – counting models with advanced component caching and implicit BCP. In Armin Biere and Carla P. Gomes, editors, Theory and Applications of Satisfiability Testing – SAT 2006, 9th International Conference, Seattle, WA, USA, August 12–15, 2006, Proceedings, volume 4121 of Lecture Notes in Computer Science, pages 424–429. Springer, 2006
    Marc Thurley
  • Complexity of the Cover Polynomial. In Proceedings of the 34th International Colloquium on Automata, Languages and Programming, ICALP 2007, volume 4596 of Lecture Notes in Computer Science, pages 801–812. Springer, 2007
    Markus Bläser and Holger Dell
  • Finding paths between graph colourings: Computational complexity and possible distances (extended abstract). In European conference on combinatorics, graph theory and applications (EuroComb 07), Sevilla, 2007, volume 29 of Electronic notes in discrete mathematics, pages 463–469. Elsevier, 2007
    P. Bonsma, L. Cereceda, J. van den Heuvel, and M. Johnson
  • Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances (extended abstract). In MFCS 07, volume 4708 of LNCS, pages 738–749. Springer, 2007
    P. Bonsma and L. Cereceda
  • Kernelizations for parameterized counting problems. In Jin Yi Cai, S. Barry Cooper, and Hong Zhu, editors, Theory and Applications of Models of Computation, 4th International Conference, TAMC 2007, Shanghai, China, May 22–25, 2007, Proceedings, volume 4484 of Lecture Notes in Computer Science, pages 703–714. Springer, 2007
    Marc Thurley
  • Most balanced minimum cuts and partially ordered knapsack (extended abstract). In 6th Cologne Twente workshop on graphs and combinatorial optimization (CTW 07), Enschede, The Netherlands, pages 17–21, Enschede, 2007. CTIT
    P. Bonsma
  • On computing the centroid of the vertices of an arrangement and related problems. In WADS, pages 519–528, 2007
    Deepak Ajwani, Saurabh Ray, Raimund Seidel, and Hans Raj Tiwary
  • On linkages in polytope graphs. Advances in Geometry, 2007
    Axel Werner and Ronald F. Wotzlaw
  • On the hardness of Minkowski addition and related operations. In Symposium on Computational Geometry, pages 306–309, 2007
    Hans Raj Tiwary
  • Quasi-randomness and algorithmic regularity for graphs with general degree distributions. In Automata, languages and programming, volume 4596 of Lecture Notes in Comput. Sci., pages 789–800. Springer, Berlin, 2007
    N. Alon, A. Coja-Oghlan, H. Hàn, M. Kang, V. Rödl, and M. Schacht
  • Thickness of bar 1-visibility graphs. In Proceedings of Graph Drawing ’06, volume 4372 of Lecture Notes Comput. Sci., pages 330–342. Springer, 2007
    Stefan Felsner and Mareike Massow
  • A 3/2-approximation algorithm for finding spanning trees with many leaves in cubic graphs (extended abstract). In WG 08, volume 5344 of LNCS, pages 66–77. Springer, 2008
    P. Bonsma and F. Zickfeld
  • A combinatorial classification of postsingularly finite complex exponential maps. Discrete and Continuous Dynamical Systems, 22(3):663–682, 2008
    Bastian Laubner, Dierk Schleicher, and Vlad Vicol
  • Algorithms for curb sets. Internship report, École Polytechnique, 2008
    Max Klimm
  • Complexity of the Bollobás–Riordan Polynomial. Exceptional Points and Uniform Reductions. In LNCS, volume 5010, pages 86–98. Springer, 2008
    Markus Bläser, Holger Dell, and Johann A. Makowsky
  • Counting hexagonal patches and independent sets in circle graphs. 2008
    Paul Bonsma and Felix Breuer
  • Distributive lattices from graphs. In Proceedings of VI. Jornadas de Matematica Discreta y Algoritmica Lleida, pages 11–23. 2008
    Stefan Felsner and Kolja B. Knauer
  • Distributive lattices on graph orientations. In Semigroups, acts and categories with applications to graphs, volume 3 of Math. Stud. (Tartu), pages 79–91. Est. Math. Soc., Tartu, 2008
    Kolja B. Knauer
  • On a cone covering problem. In CCCG, pages 171–174, 2008
    Khaled M. Elbassioni and Hans Raj Tiwary
  • On computing the shadows and slices of polytopes. CoRR
    Hans Raj Tiwary
  • On the complexity of checking self-duality of polytopes and its relations to vertex enumeration and graph isomorphism. In Symposium on Computational Geometry, pages 192–198, 2008
    Hans Raj Tiwary and Khaled M. Elbassioni
  • On the hardness of computing intersection, union and Minkowski sum of polytopes. Discrete and Computational Geometry, 40:469–479, 2008
    Hans Raj Tiwary
  • Parameters of bar k-visibility graphs. J. Graph Algorithms and Applications, 12(1):5–27, 2008
    Stefan Felsner and Mareike Massow
  • Probabilistic matching of polygons. In Proceedings of the 24th European Workshop on Computational Geometry (EuroCG), pages 255–258, Nancy, France, March 2008
    Helmut Alt, Ludmila Scharf, and Daria Schymura
  • Recoverable shortest path problems. Preprint 034-2008, Technische Universität Berlin, 2008
    Christina Büsing
  • Shortest inspection-path queries in simple polygons. In Proc. the 24th European Workshop on Computational Geometry (EuroCG’08), pages 153–156, Nancy, France, March 2008
    Christian Knauer, Günter Rote, and Lena Schlipf
  • Spanning trees with many leaves in graphs with minimum degree three. SIAM Journal on Discrete Mathematics, 22(3):920–937, 2008
    P. Bonsma
  • Spanning trees with many leaves in graphs without diamonds and blossoms. In LATIN 08, volume 4957 of LNCS, pages 531–543. Springer, 2008
    P. Bonsma and F. Zickfeld
  • TConstructions and Obstructions for Extremal Polytopes. PhD thesis, Technical University Berlin, 2008
    Raman Sanyal
  • Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree (extended abstract). In Algorithms – ESA 08, volume 5193 of LNCS, pages 222–233. Springer, 2008
    P. Bonsma and F. Dorn
  • Tight bounds and a fast FPT algorithm for directed max-leaf spanning tree. In: Halperin D., Mehlhorn K. (eds) Algorithms - ESA 2008. ESA 2008. Lecture Notes in Computer Science, vol 5193. Springer, Berlin, Heidelberg
    P. Bonsma and F. Dorn
  • Understanding the complexity of induced subgraph isomorphisms. In Luca Aceto et al. editors, Automata, Languages and Programming, 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7–11, 2008, Proceedings, Part I: Tack A: Algorithms, Automata, Complexity, and Games, volume 5125 of Lecture Notes in Computer Science, pages 587–596. Springer, 2008
    Yijia Chen, Marc Thurley, and Mark Weyer
  • A complexity dichotomy for partition functions with mixed signs. In 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, February 26–28, 2009, Freiburg, Germany, Proceedings, volume 3 of LIPIcs, pages 493–504. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Germany, 2009
    Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, and Marc Thurley
  • A lost counterexample and a problem on illuminated polytopes. August 2009, 7 pages
    Ronald F. Wotzlaw and Günter M. Ziegler
  • Capturing polynomial time on interval graphs. Preprint, November 2009, 14 pages
    Bastian Laubner
  • Characterizing the existence of potential functions in weighted congestion games. In M. Mavronicolas and V. G. Papadopoulou, editors, Proceedings of the 2nd International Symposium on Algorithmic Game Theory (SAGT), volume 5814 of Lecture Notes in Computer Science, pages 97–108. Springer, 2009
    Tobias Harks, Max Klimm, and Rolf H. Möhring
  • Chip-firing, antimatroids, and polyhedra. In Proceedings of European Conference on Combinatorics, Graph Theory and Applications, volume 34 of Electronic Notes in Discrete Mathematics, pages 9–13. 2009
    Kolja B. Knauer
  • Clause-learning algorithms with many restarts and bounded-width resolution. In Oliver Kullmann, editor, Theory and Applications of Satisfiability Testing – SAT 2009, 12th International Conference, SAT 2009, Swansea, UK, June 30 – July 3, 2009. Proceedings, volume 5584 of Lecture Notes in Computer Science, pages 114–127. Springer, 2009
    Albert Atserias, Johannes Klaus Fichte, and Marc Thurley
  • Combinatorial Stokes formulas via minimal resolutions. J. Combin. Theory Ser. A, 116(2):404–420, 2009
    Bernhard Hanke, Raman Sanyal, Carsten Schultz, and Günter M. Ziegler
  • Complexity of approximating the vertex centroid of a polyhedron. In ISAAC, pages 413–422, 2009
    Khaled M. Elbassioni and Hans Raj Tiwary
  • Computing the discrete Fréchet distance with imprecise input. In Proc. of the 12th Korea–Japan Joint Workhop on Algorithms and Computation (WAAC’09), pages 132–137, July 2009
    Hee-Kap Ahn, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron
  • Ehrhart theory, modular flow reciprocity, and the Tutte polynomial
    Raman Sanyal and Felix Breuer
  • Ehrhart theory, Modular flow reciprocity, and the Tutte polynomial. pages 1–14, 2009
    Felix Breuer and Raman Sanyal
  • Finding all minimal CURB sets. Technical Report 722, SSE/EFI Working Paper Series in Economics and Finance, 2009
    Max Klimm and Jörgen W. Weibull
  • Finding fullerene patches in polynomial time (extended abstract). In ISAAC 2009, volume 5878 of LNCS, pages 750–759. Springer, 2009
    P. Bonsma and Felix Breuer
  • Finding fullerene patches in polynomial time. In Yingfei Dong, Ding-Zhu Du, and Oscar Ibarra, editors, ISAAC 2009: Algorithms and Computation: 20th International Symposium, volume 5878 of Lecture Notes in Computer Science, pages 750–759, 2009
    Paul Bonsma and Felix Breuer
  • Finding paths between graph colourings: PSPACE-completeness and superpolynomial distances. Theoretical Computer Science, 410(50):5215–5226, 2009
    P. Bonsma and L. Cereceda
  • Fixed-parameter tractability and lower bounds for stabbing problems. CoRR, abs/0906.3896, 2009
    Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel Werner
  • Fixed-parameter tractability and lower bounds for stabbing problems. In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), pages 281–284, Brussels, Belgium, March 2009
    Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel Werner
  • Ham Sandwiches, Staircases and Counting Polynomials. Phd thesis, Freie Universität Berlin, 2009
    Felix Breuer
  • Incidence Graphs and Unneighborly Polytopes. PhD thesis, Free University Berlin, 2009
    Ronald F. Wotzlaw
  • Integer point sets minimizing average pairwise 1 distance: What is the optimal shape of a town? In Proc. of the 21st Canadian Conference on Computational Geometry (CCCG), pages 145–148, Vancouver, Canada, August 2009
    Erik D. Demaine, Sándor P. Fekete, Günter Rote, Nils Schweer, Daria Schymura, and Mariano Zelke
  • Interval stabbing problems in small integer ranges. In Y. Dong, D. Du, and O. Ibarra, editors, 20th International Symposium on Algorithms and Computation (ISAAC’09), Hawaii, USA, volume 5878, pages 163–172, 2009
    J. M. Schmidt
  • Linear Extension Graphs and Linear Extension Diameter. PhD thesis, Technical University Berlin, 2009
    Mareike Massow
  • Logics with rank operators. In LICS, pages 113–122, 2009
    A. Dawar, M. Grohe, B. Holm, and B. Laubner
  • Logics with rank operators. In Proceedings of the 24th IEEE Symposium on Logic in Computer Science, pages 113–122, 2009
    Anuj Dawar, Martin Grohe, Bjarki Holm, and Bastian Laubner
  • Measuring the similarity of geometric graphs. In Proc. 8th International Symposium on Experimental Algorithms, volume 5526 of Lecture Notes in Computer Science, pages 101–112, Dortmund, Germany, 2009. Springer
    Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura, and Fabian Stehn
  • Measuring the similarity of geometric graphs. In Proceedings of the 25th European Workshop on Computational Geometry (EuroCG), Brussels, Belgium, March 2009
    Otfried Cheong, Joachim Gudmundsson, Hyo-Sil Kim, Daria Schymura, and Fabian Stehn
  • Note on strong refutation algorithms for random k-sat formulas. In Proceedings of LAGOS, volume 35 of Electron. Notes Discrete Math., pages 157–162. Elsevier, 2009
    H. Hàn, Y. Person, and M. Schacht
  • On Kalai’s conjectures concerning centrally symmetric polytopes. Discrete Comput. Geom., 41(2):183–198, 2009
    Raman Sanyal, Axel Werner, and Günter M. Ziegler
  • On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math., 23(2):732–748, 2009
    H. Hàn, Y. Person, and M. Schacht
  • On perfect matchings in uniform hypergraphs with large minimum vertex degree. SIAM J. Discrete Math., 23(2):732–748, 2009
    H. Hàn, Y. Person, and M. Schacht
  • Polynomial time recognition of uniform cocircuit graphs. In LAGOS’09 – V Latin-American algorithms, graphs, and optimization symposium. Papers from the symposium, Gramado, Brazil, November 3–7, 2009., pages 29–34. 2009
    Ricardo Gómez Aiza, Juan José Montellano-Ballesteros, Ricardo Strausz, and Kolja Knauer
  • Polynomial time recognition of uniform cocircuit graphs. In Proceedings of V Latin-American Algorithms, Graphs and Optimization Symposium, volume 35 of Electronic Notes in Discrete Mathematics, pages 29–34. 2009
    Ricardo Gomez, Kolja B. Knauer, Juan Jose Montellano-Ballesteros, and Ricardo Strausz
  • Staircases in Z2. 32 pages
    Felix Breuer and Frederik von Heymann
  • Strong Nash equilibria in games with the lexicographical improvement property. In S. Leonardi, editor, Proceedings of the 5th International Workshop on Internet and Network Economics (WINE), volume 5929 of Lecture Notes in Computer Science, pages 463–470. Springer, 2009
    Tobias Harks, Max Klimm, and Rolf H. Möhring
  • The Complexity of Partition Functions. PhD thesis, Free University Berlin, 2009
    Marc Thurley
  • The exact subgraph recoverable robust shortest path problem. In Raviandra K. Ahuja, Rolf H. Möhring, and Christos D. Zaroliagis, editors, Robust and Online Large-Scale Optimization, volume 5868 of Lecture Notes in Computer Science, pages 235–254. Springer, 2009
    Christina Büsing
  • The parameterized complexity of some geometric problems in unbounded dimension. CoRR, abs/0906.3469, 2009
    Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel Werner
  • Topological obstructions for vertex numbers of Minkowski sums. J. Combin. Theory Ser. A, 116(1):168–179, 2009
    Raman Sanyal
  • Topological obstructions for vertex numbers of Minkowski sums. J. Combin. Theory Ser. A, 116(1):168–179, 2009
    Raman Sanyal
  • ULD-lattices and ∆-bonds. Comb. Probab. Comput., 18(5):707–724, 2009
    Stefan Felsner and Kolja Knauer
  • ULD-lattices and ∆-bonds. Combin. Probab. Comput., 18(5):707–724, 2009
    Stefan Felsner and Kolja B. Knauer
  • Uneven Splitting of Ham Sandwiches. Discrete and Computational Geometry, 2009
    Felix Breuer
  • Viewing counting polynomials as Hilbert functions via Ehrhart theory
    Felix Breuer and Aaron Dall
  • Capturing polynomial time on interval graphs. In LICS, pages 199–208, 2010
    B. Laubner
  • Characterizing the existence of pure Nash equilibria in weighted congestion games. Technical Report 001-2010, Technical University, Berlin, 2010
    Tobias Harks and Max Klimm
  • Computing pure Nash and strong equilibria in bottleneck congestion games. In M. de Berg and U. Meyer, editors, Proceedings of the 18th European Symposium on Algorithms (ESA), volume 6347 of Lecture Notes in Computer Science, pages 29–38, 2010
    Tobias Harks, Martin Hoefer, Max Klimm, and Alexander Skopalik
  • Computing the discrete Fréchet distance with imprecise input. In Otfried Cheong, Kyung-Yong Chwa, and Kunsoo Park, editors, Proceedings of the 21st International Symposium on Algorithms and Computation (ISAAC 2010), volume 6507 of Lecture Notes in Computer Science, pages 422–433. Springer-Verlag, Berlin/Heidelberg, Germany, 2010
    Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron
  • Computing the discrete Fréchet distance with imprecise input. In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), pages 13–16, Dortmund, Germany, 2010
    Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron
  • Construction and analysis of projected deformed products. Discrete Comput. Geom., 43(2):412–435, 2010
    Raman Sanyal and Günter M. Ziegler
  • Construction sequences and certifying 3-connectedness. In 27th International Symposium on Theoretical Aspects of Computer Science (STACS’10), Nancy, France, pages 633–644, 2010
    J. M. Schmidt
  • Cubic time recognition of cocircuit graphs of uniform oriented matroids. January 2010, 9 pages
    Stefan Felsner, Ricardo Gomez, Kolja B. Knauer, Juan Jose Montellano-Ballesteros, and Ricardo Strausz
  • Dirac-type results for loose Hamilton cycles in uniform hypergraphs. J. Combin. Theory Ser. B, 100(3):332–346, 2010
    H. Hàn and M. Schacht
  • Dirac-type results for loose Hamilton cycles in uniform hypergraphs. Journal of Combinatorial Theory (B), 100:332–346, 2010
    H. Hàn and M. Schacht
  • Extremal Hypergraph Theory and Algorithmic Regularity Lemma for Sparse Graphs. PhD thesis, Humboldt University of Berlin, 2010
    Hiêp Hàn
  • Graphen- und Netzwerkoptimierung. Spektrum Akademischer Verlag Heidelberg, 2010
    C. Büsing
  • Hardness of discrepancy and related problems parameterized by the dimension. In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), Dortmund, Germany, March 2010
    Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner
  • Interval graphs: Canonical representation in logspace. Electronic Colloquium on Computational Complexity (ECCC), 17:43, 2010
    J. Köbler, S. Kuhnert, B. Laubner, and O. Verbitsky
  • Interval graphs: Canonical representation in logspace. In ICALP (1), pages 384–395, 2010
    J. Köbler, S. Kuhnert, B. Laubner, and O. Verbitsky
  • Largest inscribed rectangles in convex polygons (extended abstract). In EuroCG’10, volume 26, pages 201–204, 2010
    Christian Knauer, Lena Schlipf, Jens M. Schmidt, and Hans Raj Tiwary
  • Largest inscribed rectangles in simple polygons. In Proc. of the 26th European Workshop on Computational Geometry (EuroCG’10), volume 26, pages 13–16, Dortmund, Germany, March 2010
    Christian Knauer, Lena Schlipf, Jens M. Schmidt, and Hans Raj Tiwary
  • Largest inscribed rectangles in simple polygons. In Proceedings of the 26th European Workshop on Computational Geometry (EuroCG), pages 201–204, Dortmund, Germany, 2010
    Christian Knauer, Lena Schlipf, Jens Schmidt, and Hans Tiwary
  • Lattices and Polyhedra from Graphs. PhD thesis, Technical University Berlin, 2010
    Kolja B. Knauer
  • Most balanced minimum cuts. Discrete Applied Mathematics,, 158(4):261–276, 2010
    P. Bonsma
  • On the existence of pure Nash equilibria in weighted congestion games. In S. Abramsky et al. editors, Proceedings of the 37th International Colloquium on Automata, Languages and Programming (ICALP), volume 6198 of Lecture Notes in Computer Science, pages 79–89. Springer, 2010
    Tobias Harks and Max Klimm
  • Point sets with planar embeddings of cubic, connected graphs. In Jiří Fink, editor, KAM-DIMATIA Series 959. Charles University, Prague, 2010
    J. M. Schmidt
  • Polynomial bounds on the rectangle slicing number. CoRR, abs/1004.3381, 2010
    Daniel Werner
  • Probabilistic matching of planar regions. Computational Geometry, Theory and Applications (CGTA), 43(2):99–114, 2010. Special Issue on the 24th European Workshop on Computational Geometry (EuroCG’08)
    Helmut Alt, Ludmila Scharf, and Daria Schymura
  • Quasi randomness and algorithmic regularity for graphs with general degree distributions. SIAM J. Comput., 39(6):2336–2362, 2010
    Noga Alon, Amin Coja-Oghlan, Hiêp Hàn, Mihyun Kang, Vojtěch Rödl, and Mathias Schacht
  • Toroidal embeddings of right groups. Thai J. Math., 8(3):483–490, 2010
    Kolja Knauer and Ulrich Knauer
  • Approximating Tverberg points in linear time for any fixed dimension. CoRR, abs/1107.0104, 2011
    Wolfgang Mulzer and Daniel Werner
  • CD8(+) T-cell response promotes evolution of hepatitis C virus nonstructural proteins. Gastroenterology, 140(7):2064–2073, 2011
    Marianne Ruhl, Torben Knuschke, Kevin Schewior, Lejla Glavinic, Christoph Neumann-Haefelin, Dae-In Chang, Marina Klein, Falko M Heinemann, Hannelore Hanneloreoff, Manfred Wiese, Peter A Horn, Sergei Viazov, Ulrich Spengler, Michael Roggendorf, Norbert Scherbaum, Jacob Nattermann, Daniel Hoffmann, and Jörg Timm
  • Characterizing the existence of potential functions in weighted congestion games. Theory of Computing Systems, 49(1):46–70, 2011
    Tobias Harks, Max Klimm, and Rolf H. Möhring
  • Computing barrier resilience for line segments is NP-hard and APX-hard. In Proc.of the 14th Korea-Japan Joint Workhop on Algorithms and Computation (WAAC 2011), 2011
    Otfried Cheong, Hyo-Sil Kim, and Lena Schlipf
  • Congestion games with variable demands. In Krzysztof R. Apt, editor, Proceedings of the 13th Conference On Theoretical Aspects of Rationality and Knowledge (TARK), pages 111–120, 2011
    Tobias Harks and Max Klimm
  • Convex transversals. In Frank Dehne, John Iacono, and Jörg-Rüdiger Sack, editors, Algorithms and Data Structures, volume 6844 of Lecture Notes in Computer Science, pages 49–60. Springer Berlin / Heidelberg, 2011
    Esther Arkin, Claudia Dieckmann, Christian Knauer, Joseph Mitchell, Valentin Polishchuk, Lena Schlipf, and Shang Yang
  • Covering and piercing disks with two centers. In Proceedings of the 27th European Workshop on Computational Geometry (EuroCG), pages 63–66, Morschach, Switzerland, 2011
    Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Hyeon-Suk Na, Lena Schlipf, Chan-Su Shin, and Antoine Vigneron
  • Covering and piercing disks with two centers. In Takao Asano, Shin ichi Nakano, Okamoto Yoshio, and Osamu Watanabe, editors, Algorithms and Computation, volume 7074, pages 50–59. Springer Berlin/Heidelberg, 2011
    Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, and Antoine Vigneron
  • Cubic time recognition of cocircuit graphs of uniform oriented matroids. Eur. J. Comb., 32(1):60–66, 2011
    Stefan Felsner, Ricardo Gómez, Kolja Knauer, Juan José Montellano-Ballesteros, and Ricardo Strausz
  • Demand allocation games: Integrating discrete and continuous strategy spaces. In Ning Chen, Edith Elkind, and Elias Koutsoupias, editors, Proceedings of the 7th International Workshop on Internet and Network Economics (WINE), pages 194–205, 2011
    Tobias Harks and Max Klimm
  • Distributive lattices, polyhedra, and generalized flows. Eur. J. Comb., 32(1):45–59, 2011
    Stefan Felsner and Kolja Knauer
  • Equality of ordinary and symbolic powers of Stanley–Reisner ideals. Journal of Algebra, 328:77–93, 2011
    Ngo Viet Trung and Tran Manh Tuan
  • Erdös-szekeres and testing weak epsilon-nets are NP-hard in 3 dimensions – and what now? CoRR, abs/1111.5979, 2011
    Christian Knauer and Daniel Werner
  • Hardness of discrepancy computation and epsilon-net verification in high dimension. CoRR, abs/1103.4503, 2011
    Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner
  • How to eat 4/9 of a pizza. Discrete Math., 311(16):1635– 1645, 2011
    Kolja Knauer, Piotr Micek, and Torsten Ueckerdt
  • Interval graphs: Canonical representations in logspace. SIAM J. Comput., 40(5):1292–1315, 2011
    Johannes Köbler, Sebastian Kuhnert, Bastian Laubner, and Oleg Verbitsky
  • L-recursion and a new logic for logarithmic space. In Computer Science Logic, 25th International Workshop / 20th Annual Conference of the EACSL, CSL 2011, September 12-15, 2011, Bergen, Norway, Proceedings, pages 277–291, 2011
    Martin Grohe, Berit Grußien, André Hernich, and Bastian Laubner
  • Line planning, path constrained network flow and inapproximability. Networks, 57:106-113, 2011
    C. Büsing and S. Stiller
  • Local connectivity tests to identify wormholes in wireless networks. In Proceedings of the Twelfth ACM International Symposium on Mobile Ad Hoc Networking and Computing, page 13. ACM, 2011
    Xiaomeng Ban, Rik Sarkar, and Jie Gao
  • Low distortion delaunay embedding of trees in hyperbolic plane. In Graph Drawing, pages 355–366. Springer Berlin Heidelberg, 2011
    Rik Sarkar
  • Matroid secretary problem in the random assignment model. In Proceedings of the 22nd Annual ACM–SIAM Symposium on Discrete Algorithms (SODA), pages 1275–1284, 2011
    J. A. Soto
  • On the computational complexity of ham-sandwich cuts, helly sets, and related problems. In 28th International Symposium on Theoretical Aspects of Computer Science, STACS 2011, March 10-12, 2011, Dortmund, Germany, pages 649–660, 2011
    Christian Knauer, Hans Raj Tiwary, and Daniel Werner
  • On variants of the matroid secretary problem. In Proceedings of the 19th European Conference on Algorithms (ESA), pages 335–346, Berlin, Heidelberg, 2011. Springer-Verlag
    S. Oveis Gharan and J. Vondrák
  • Optimal cost sharing protocols for scheduling games. In Proceedings of the 12th ACM conference on Electronic Commerce, pages 285–294. ACM, 2011
    P. von Falkenhausen and T. Harks
  • Optimal file distribution in peer-topeer networks. In T. Asano, S. Nakano, Y. Okamoto, and O. Watanabe, editors, Proceedings of the 22nd International Symposium on Algorithms and Computation (ISAAC), pages 210–219, 2011
    Kai Goetzmann, Tobias Harks, Max Klimm, and Konstantin Miller
  • Probabilistic matching of solid shapes in arbitrary dimension. PhD thesis, Free University Berlin, 2011
    Daria Schymura
  • Recoverable robust knapsacks: Gamma-scenarios. In International Network Optimization Conference, INOC 2011, volume 6701, pages 583–588, 2011
    C. Büsing, A. M. C. A. Koster, and M. Kutschka
  • Recoverable Robustness in Combinatorial Optimization (PhD thesis). Cuvillier Verlag, 2011
    C. Büsing
  • Sparse Instances of Hard Problems. PhD thesis, Humboldt University of Berlin, 2011
    Holger Dell
  • Structure and Constructions of 3-Connected Graphs. PhD thesis, Freie Universität Berlin, Germany, 2011
    J. M. Schmidt
  • The structure of graphs and new logics for the characterization of Polynomial Time. PhD thesis, Humboldt University of Berlin, 2011
    Bastian Laubner
  • A lower bound for shallow partitions. CoRR, abs/1201.2267, 2012
    Wolfgang Mulzer and Daniel Werner
  • Approximating Tverberg points in linear time for any fixed dimension. In Symposuim on Computational Geometry 2012, SoCG ’12, Chapel Hill, NC, USA, June 17–20, 2012, pages 303– 310, 2012
    Wolfgang Mulzer and Daniel Werner
  • Arvin, Berit und die Lastwagen. In Besser als Mathe, pages 151–160. Springer Science + Business Media, dec 2012
    Falk Ebert and Anita Liebenau
  • Bijective mappings preserving intersecting antichains for k-valued cubes. Discrete Math., 312:2023–2026, 2012
    R. Glebov
  • Characterization of polytopes via tilings and similar pieces. Discrete Comput. Geom., 47(2):424–429, 2012
    Karim Adiprasito
  • Competition for Resources: The Equilibrium Existence Problem in Congestion Games. PhD thesis, Technical University Berlin, 2012
    Max Klimm
  • Computing the discrete Fréchet distance with imprecise input. Int. J. Comput. Geometry Appl., 22(1):27–44, 2012
    Hee-Kap Ahn, Christian Knauer, Marc Scherfenberg, Lena Schlipf, and Antoine Vigneron
  • Counting Hexagonal Patches and Independent Sets in Circle Graphs. Algorithmica, 63(3):645–671, 2012
    Paul Bonsma and Felix Breuer
  • Fast strategies in maker–breaker games played on random boards. Combinator. Probab. Comp., 21(06):897–915, sep 2012
    Dennis Clemens, Asaf Ferber, Michael Krivelevich, and Anita Liebenau
  • Hardness of discrepancy computation and -net verification in high dimension. J. Complexity, 28(2):162–176, 2012
    Panos Giannopoulos, Christian Knauer, Magnus Wahlström, and Daniel Werner
  • Infinite curvature on typical convex surfaces. Geom. Dedicata, 159:267–275, 2012
    Karim Adiprasito
  • L-recursion and a new logic for logarithmic space. Logical Methods in Computer Science, 9(1), 2012
    Martin Grohe, Berit Grußien, André Hernich, and Bastian Laubner
  • Large curvature on typical convex surfaces. J. Conv. Anal., 19(2):385–391, 2012
    Karim Adiprasito and Tudor Zamfirescu
  • Largest inscribed rectangles in convex polygons. J. Discrete Algorithms, 13:78–85, 2012
    Christian Knauer, Lena Schlipf, Jens M. Schmidt, and Hans Raj Tiwary
  • Multi-cluster complexes. Discrete Math. Theor. Comput. Sci. Proc. FPSAC, 0(01):1–8, 2012
    Cesar Ceballos, Jean-Philippe Labbé, and Christian Stump
  • Non-projectability of polytope skeleta. Adv. Math., 229(1):79–101, 2012
    Thilo Rörig and Raman Sanyal
  • On associahedra and related topics. PhD thesis, Free University Berlin, 2012
    Cesar Ceballos
  • On Hamilton cycles and other spanning structures. PhD thesis, Free University Berlin, 2012
    R. Glebov
  • On the bend-number of planar and outerplanar graphs. In LATIN 2012: Theoretical informatics. 10th Latin American symposium, Arequipa, Peru, April 16–20, 2012. Proceedings, pages 458–469. 2012
    Daniel Heldt, Kolja Knauer, and Torsten Ueckerdt
  • On the bend-number of planar and outerplanar graphs. In Proceedings of the Tenth Latin American Symposium on Theoretical Informatics, LATIN ’12, pages 458–469, 2012
    Daniel Heldt, Kolja B. Knauer, and Torsten Ueckerdt
  • On the existence of pure Nash equilibria in weighted congestion games. Mathematics of Operations Research, 37(3):419–436, 2012
    Tobias Harks and Max Klimm
  • Optimization over integers with robustness in cost and few constraints. In Roberto Solis-Oba and Giuseppe Persiano, editors, Approximation and Online Algorithms (WAOA 2011), volume 7164 of Lecture Notes in Computer Science, pages 89–101. Springer Berlin / Heidelberg, 2012
    Kai-Simon Goetzmann, Sebastian Stiller, and Claudio Telha
  • Realizing the associahedron: Mysteries and questions. In Folkert Müller-Hoissen, Jean Marcel Pallo, and Jim Stasheff, editors, Associahedra, Tamari Lattices and Related Structures, number 299 in Progress in Mathematics, pages 119–127. Springer Basel, January 2012
    Cesar Ceballos and Günter M. Ziegler
  • Sparse universal graphs. European J. Combin., 33:544–555, 2012
    R. Glebov, Y. Person, and W. Weps
  • Weak quasi-randomness for uniform hypergraphs. Random Structures Algorithms, 40(1):1–38, 2012
    D. Conlon, H. Hàn, Y. Person, and M. Schacht
  • Acyclic systems of permutations and fine mixed subdivisions of simplices. Discrete & Computational Geometry, 49(3):485–510, 2013
    Federico Ardila and Cesar Ceballos
  • Advances on matroid secretary problems: Free order model and laminar case. In Michel X. Goemans and José R. Correa, editors, IPCO, volume 7801 of Lecture Notes in Computer Science, pages 254–265. Springer, 2013
    Patrick Jaillet, José A. Soto, and Rico Zenklusen
  • Algorithms for tolerated Tverberg partitions. In Algorithms and Computation, volume 8283 of Lecture Notes in Computer Science, pages 295–305. Springer Berlin Heidelberg, 2013
    Wolfgang Mulzer and Yannik Stein
  • Apollonian ball packings and stacked polytopes. June 2013. 20 pp
    Hao Chen
  • Approximating Tverberg points in linear time for any fixed dimension. Discrete & Computational Geometry, 50(2):520–535, 2013
    Wolfgang Mulzer and Daniel Werner
  • Arc consistency and friends. Journal of Logic and Computation, 23(1):87–108, 2013
    Hubie Chen, Víctor Dalmau, and Berit Grußien
  • Ball Packings and Lorentzian Discrete Geometry. PhD thesis, Free University Berlin, 2013
    Hao Chen
  • Building spanning trees quickly in maker-breaker games. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, pages 365–370. Springer Science + Business Media, 2013
    Dennis Clemens, Asaf Ferber, Roman Glebov, Dan Hefetz, and Anita Liebenau
  • Computational Aspects of some Problems from Discrete Geometry in Higher Dimensions. PhD thesis, Free University Berlin, 2013
    Daniel Werner
  • Covering and piercing disks with two centers. Comput. Geom., 46(3):253–262, 2013
    Hee-Kap Ahn, Sang-Sub Kim, Christian Knauer, Lena Schlipf, Chan-Su Shin, and Antoine Vigneron
  • Degrees of generators of phylogenetic semigroups on graphs. Cent. Eur. J. Math., 11(9):1577–1592, 2013
    W. Buczyńska, J. Buczyński, K. Kubjas, and M. Michałek
  • Denominator vectors and compatibility degrees in cluster algebras of finite type. Discrete Math. Theor. Comput. Sci. Proc. FPSAC, 0(01):85–96, 2013
    Cesar Ceballos and Vincent Pilaud
  • Designing Mechanisms for Good Equilibria. PhD thesis, Technical University Berlin, 2013
    Philipp von Falkenhausen
  • Differential forms for target tracking and aggregate queries in distributed networks. Networking, IEEE/ACM Transactions on, 21(4):1159–1172, 2013
    Rik Sarkar and Jie Gao
  • Distributed and compact routing using spatial distributions in wireless sensor networks. ACM Transactions on Sensor Networks (TOSN), 9(3):32, 2013
    Rik Sarkar, Xianjin Zhu, and Jie Gao
  • Fixed parameter complexity and approximability of norm maximization. CoRR, abs/1307.6414, 2013
    Christian Knauer, Stefan König, and Daniel Werner
  • Fixed-parameter tractability and lower bounds for stabbing problems. Comput. Geom., 46(7):839–860, 2013
    Panos Giannopoulos, Christian Knauer, Günter Rote, and Daniel Werner
  • Matroid secretary problem in the random-assignment model. SIAM J. Comput., 42(1):178–211, 2013
    José A. Soto
  • Methods from Differential Geometry in Polytope Theory. PhD thesis, Free University Berlin, 2013
    Karim Adiprasito
  • On the computational complexity of erdös-szekeres and related problems in ↑↑3. In Algorithms – ESA 2013 – 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings, pages 541–552, 2013
    Panos Giannopoulos, Christian Knauer, and Daniel Werner
  • On the number of edges of fan-crossing free graphs. In Algorithms and Computation: 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings, volume 8283, page 163. Springer, 2013
    Otfried Cheong, Sariel Har-Peled, Heuna Kim, and Hyo-Sil Kim
  • On the number of Hamilton cycles in sparse random graphs. SIAM J. Discrete Math., 27:27–42, 2013
    R. Glebov and M. Krivelevich
  • On the threshold bias in the oriented cycle game. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, pages 359–363. Springer Science + Business Media, 2013
    Dennis Clemens and Anita Liebenau
  • Optimal cost sharing for capacitated facility location games. In Proceedings of the 12th Cologne-Twente Workshop on Graphs and Combinatorial Optimization, pages 99–102. CTIT University of Twente, 2013
    Philipp von Falkenhausen and Tobias Harks
  • Optimal cost sharing for resource selection games. Mathematics of Operations Research, 38(1):184–208, 2013
    Philipp von Falkenhausen and Tobias Harks
  • Quantitative comparative statics for a multimarket paradox. In Proceedings of the 9th International Conference on Web and Internet Economics, volume 8289 of LNCS, pages 230–231. Springer, 2013
    Tobias Harks and Philipp von Falkenhausen
  • Stabbing and Covering Geometric Objects in the Plane. PhD thesis, Free University Berlin, 2013
    Lena Schlipf
  • The biased odd cycle game. Electron. J. Combin., 20:P9, 2013
    A. Ferber, R. Glebov, M. Krivelevich, H. Liu, C. Palmer, T. Valla, and M. Vizer
  • The Power of Compromise. Reference Point Methods and Approximation in Multicriteria Optimization. Coga, TU Berlin, 2013
    Kai-Simon Goetzmann
  • A proof of the oja depth conjecture in the plane. Comput. Geom., 47(6):668–674, 2014
    Nabil H. Mustafa, Hans Raj Tiwary, and Daniel Werner
  • Advantage in the discrete Voronoi game. J. Graph Algorithms Appl., 18:439–457, 2014
    D. Gerbner, V. Mészáros, D. Pálvólgyi, A. Pokrovskiy, and G. Rote
  • Algorithms for tolerant Tverberg partitions. International Journal of Computational Geometry & Applications, 24(04):261–273, 2014
    Wolfgang Mulzer and Yannik Stein
  • An on-line competitive algorithm for coloring p8 -free bipartite graphs. In Algorithms and Computation, volume 8889 of Lecture Notes in Computer Science, pages 516–527. Springer International Publishing, 2014
    Piotr Micek and Veit Wiechert
  • Arithmetic of marked order polytopes, monotone triangle reciprocity, and partial colorings. SIAM Journal on Discrete Mathematics, 28(3):1540–1558, 2014
    Katharina Jochemko and Raman Sanyal
  • Combinatorial stratifications and minimality of 2-arrangements. J. Topol., 7(4):1200–1220, 2014
    Karim Adiprasito
  • Combinatorial voter control in elections. In Proceedings of the 39th International Symposium on Mathematical Foundations of Computer Science (MFCS ’14), volume 8635 of LNCS, pages 153–164. Springer, 2014
    Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon
  • Convex transversals. Comput. Geom., 47(2):224–239, 2014
    Esther M. Arkin, Claudia Dieckmann, Christian Knauer, Joseph S.B. Mitchell, Valentin Polishchuk, Lena Schlipf, and Shang Yang
  • Conflict-free coloring of graphs. Combin. Probab. Comput., 23:434–448, 2014
    R. Glebov, T. Szabó, and G. Tardos
  • Edge-intersection graphs of grid paths: The bendnumber. Discrete Appl. Math., 167:144–162, 2014
    Daniel Heldt, Kolja Knauer, and Torsten Ueckerdt
  • Edge-intersection graphs of grid paths: The bendnumber. Discrete Applied Mathematics, 167:144–162, 2014
    Daniel Heldt, Kolja B. Knauer, and Torsten Ueckerdt
  • Erratum to: Antimatroids and balanced pairs. Order, 32(1):145–146, 2014
    David Eppstein and Veit Wiechert
  • Extremal edge polytopes. Electronic Journal of Combinatorics, 21(2), 2014
    T. Tran and G. M. Ziegler
  • Extremal hypergraphs for ryser’s conjecture i: Connectedness of line graphs of bipartite graphs, January 2014
    Penny Haxell, Lothar Narins, and Tibor Szabó
  • Extremal Hypergraphs for Ryser’s Conjecture. PhD thesis, Free University Berlin, 2014
    L. Narins
  • Extremal results for odd cycles in sparse pseudorandom graphs. Combinatorica, 34, 2014
    Elad Aigner-Horev, Hiêp Hàn, and Mathias Schacht
  • Fp is locally like C. J. London Math. Soc., 89(3):724–744, 2014
    Codrut Grosu
  • Geometric methods of information storage and retrieval in sensor networks. In The Art of Wireless Sensor Networks, pages 465–493. Springer Berlin Heidelberg, 2014
    Rik Sarkar
  • Graphs without proper subgraphs of minimum degree 3 and short cycles, August 2014
    Lothar Narins, Alexey Pokrovskiy, and Tibor Szabó
  • How many colors guarantee a rainbow matching? Electron. J. Combin., 21:P1.27, 2014
    R. Glebov, B. Sudakov, and T. Szabó
  • Limit directions for Lorentzian Coxeter groups. March 2014. 20 pp
    Hao Chen and Jean-Philippe Labbé
  • Limit directions of Lorentzian Coxeter groups. preprint, 20 pp., March 2014
    Hao Chen and Jean-Philippe Labbé
  • On covering expander graphs by Hamilton cycles. Random Structures Algorithms, 44:183–200, 2014
    R. Glebov, M. Krivelevich, and T. Szabó
  • On the algebraic and topological structure of the set of Turán densities
    Codrut Grosu
  • On the bend-number of planar and outerplanar graphs. Discrete Applied Mathematics, 179:109–119, 2014
    Daniel Heldt, Kolja B. Knauer, and Torsten Ueckerdt
  • On the number of edges of fan-crossing free graphs. Algorithmica, 73(4):673–695, 2014
    Otfried Cheong, Sariel Har-Peled, Heuna Kim, and Hyo-Sil Kim
  • Packing segments in a convex 3-polytope is np-hard. In Abstracts 30th European Workshop on Computational Geometry (EuroCG), 2014
    Michael Gene Dobbins and Heuna Kim
  • Partitioning edge-coloured complete graphs into monochromatic cycles and paths. J. Graph Algorithms Appl., 106:70–97, 2014
    A. Pokrovskiy
  • Removal and Stability for Erdos-Ko-Rado
    S. Das and T. Tran
  • Routing games with progressive filling. In IEEE International Conference on Computer Communications (INFOCOM), pages 352–360, 2014
    Tobias Harks, Martin Hoefer, Kevin Schewior, and Alexander Skopalik
  • Subword complexes, cluster complexes, and generalized multi-associahedra. J. Algebraic Combin., 39(1):17–51, 2014
    Cesar Ceballos, Jean-Philippe Labbé, and Christian Stump
  • The complexity of degree anonymization by vertex addition. In Proceedings of the 10th International Conference on Algorithmic Aspects in Information and Management (AAIM ’14), volume 8546 of LNCS, pages 44–55. Springer, 2014
    Robert Bredereck, Vincent Froese, Sepp Hartung, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon
  • The complexity of degree anonymization by vertex addition.In: Gu Q., Hell P., Yang B. (eds) Algorithmic Aspects in Information and Management. AAIM 2014. Lecture Notes in Computer Science, vol 8546. Springer, Cham
    Robert Bredereck, Vincent Froese, Sepp Hartung, André Nichterlein, Rolf Niedermeier, and Nimrod Talmon
  • The Hirsch conjecture holds for normal flag complexes. Math. Oper. Res., 39(4):1340–1348, 2014
    Karim Adiprasito and Bruno Benedetti
  • What is Ramsey-equivalent to a clique? Journal of Combinatorial Theory, Series B, 109:120–133, nov 2014
    Jacob Fox, Andrey Grinshpun, Anita Liebenau, Yury Person, and Tibor Szabó
  • A 2-competitive algorithm for online convex optimization with switching costs. In Workshop on Approximation Algorithms for Combinatorial Optimization Problems (APPROX), pages 96–109, 2015
    Nikhil Bansal, Anupam Gupta, Ravishankar Krishnaswamy, Kirk Pruhs, Kevin Schewior, and Clifford Stein
  • A density turán theorem, September 2015
    Lothar Narins and Tuan Tran
  • A Hopf algebra of subword complexes. 2015
    Nantel Bergeron and Cesar Ceballos
  • A linear bound on the Manickam–Miklós–Singhi Conjecture. Journal of Combinatorial Theory, Series A, Volume 133, July 2015, Pages 280-306
    A. Pokrovskiy
  • A new lower bound for the Towers of Hanoi problem
    Codrut Grosu
  • A flag vector of a 3-sphere that is not the flag vector of a 4-polytope
    Philip Brinkmann and Günter M. Ziegler
  • Algorithmic Aspects of Manipulation and Anonymization in Social Choice and Social Networks. PhD thesis, Technical University Berlin, 2015
    Nimrod Talmon
  • An Alexander-type duality for valuations. Proc. Amer. Math. Soc., 143(2):833–843, 2015
    Karim Adiprasito and Raman Sanyal
  • Approximability and parameterized complexity of multicover by c -intervals. Information Processing Letters, 115(10):744–749, 2015
    René van Bevern, Jiehua Chen, Falk Hüffner, Stefan Kratsch, Nimrod Talmon, and Gerhard J. Woeginger
  • Approximate k-flat nearest neighbor search. In Proceedings of the 47th Annual ACM on Symposium on Theory of Computing (STOC 2015), pages 783–792. ACM, 2015
    Wolfgang Mulzer, Huy L. Nguyên, Paul Seiferth, and Yannik Stein
  • Biased games on random boards. Random Structures Algorithms, 46:651–676, 2015
    A. Ferber, R. Glebov, M. Krivelevich, and A. Naor
  • Building spanning trees quickly in maker-breaker games. SIAM J. Discrete Math., 29(3):1683–1705, jan 2015
    Dennis Clemens, Asaf Ferber, Roman Glebov, Dan Hefetz, and Anita Liebenau
  • Building spanning trees quickly in makerbreaker games. SIAM J. Discrete Math., 29:1683–1705, 2015
    D. Clemens, A. Ferber, R. Glebov, D. Hefetz, and A. Liebenau
  • Cluster algebras of type D4 , tropical planes, and the positive tropical grassmannian
    Sarah Brodsky, Jean-Philippe Labbé, and Cesar Ceballos
  • Cluster algebras of type D: pseudotriangulations approach. The Electronic Journal of Combinatorics, 22(4):P4.44, December 2015
    Cesar Ceballos and Vincent Pilaud
  • Combinatorial voter control in elections. Theoretical Computer Science, 589:99–120, 2015
    Laurent Bulteau, Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon
  • Combinatorics of the zeta map on rational dyck paths. Journal of Combinatorial Theory, Series A
    Cesar Ceballos, Tom Denton, and Christopher Hanusa
  • Compactness and finite forcibility of graphons
    R. Glebov, D. Král’, and J. Volec
  • Comparable pairs in families of sets. J. Combin. Theory Ser. B, 115:164–185, 2015
    N. Alon, S. Das, R. Glebov, and B. Sudakov
  • Complexity and algorithms in matching problems under preferences. PhD thesis, Technical University Berlin, 2015
    Ágnes Cseh
  • Computational Aspects of the Colorful Carathéodory Theorem. In 31st International Symposium on Computational Geometry (SoCG 2015), volume 34 of Leibniz International Proceedings in Informatics (LIPIcs), pages 44–58. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2015
    Wolfgang Mulzer and Yannik Stein
  • Computing Maximal Copies of Polyhedra Contained in a Polyhedron. Experimental Mathematics, 24(1):98–105, 2015
    Moritz Firsching
  • Connexité des graphes de pseudo-variétés d’un point de vue algébrique. C. R., Math., Acad. Sci. Paris, 353(12):1061–1065, 2015
    Karim Adiprasito, Afshin Goodarzi, and Matteo Varbaro
  • Creating cycles in Walker-Breaker games
    D. Clemens and T. Tran
  • Denominator vectors and compatibility degrees in cluster algebras of finite type. Trans. Amer. Math. Soc., 367(2):1421–1439, 2015
    Cesar Ceballos and Vincent Pilaud
  • Derived subdivisions make every PL sphere polytopal. Isr. J. Math., 208:443–450, 2015
    Karim Adiprasito and Ivan Izmestiev
  • Diameters and geodesic properties of generalizations of the associahedron. 27th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2015), Jul 2015, Daejeon, South Korea. DMTCS Proceedings, pp.345-356
    Cesar Ceballos, Thibault Manneville, Vincent Pilaud, and Lionel Pournin
  • Distance geometry for kissing spheres. Linear Algebra Appl., 479:185–201, 2015
    Hao Chen
  • Dyck path triangulations and extendability. Journal of Combinatorial Theory, Series A Volume 131, April 2015, Pages 187-208
    Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento
  • Dyck path triangulations and extendability. Journal of Combinatorial Theory, Series A, 131:187–208, 2015
    Cesar Ceballos, Arnau Padrol, and Camilo Sarmiento
  • Elections with few candidates: Prices, weights, and covering problems. In Proceedings of the 4th International Conference on Algorithmic Decision Theory (ADT ’15), pages 414–431. Springer, 2015
    Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, Piotr Skowron, and Nimrod Talmon
  • Elections with few voters: Candidate control can be easy. In Proceedings of the Twenty-Ninth AAAI Conference on Artificial Intelligence (AAAI ’15), pages 2045–2051. AAAI Press, 2015
    Jiehua Chen, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon
  • Even more infinite ball packings from lorentzian root systems. September 2015. 26 pp
    Hao Chen
  • Fan realizations of type A subword complexes and multi-associahedra of rank 3. Discrete & Computational Geometry, 54(1):195–231, April 2015
    Nantel Bergeron, Cesar Ceballos, and Jean-Philippe Labbé
  • Fan realizations of type A subword complexes and multi-associahedra of rank 3. Discrete Comput. Geom., 54(1):195–231, 2015
    Nantel Bergeron, Cesar Ceballos, and Jean-Philippe Labbé
  • Few Alexandrov surfaces are Riemann. J. Nonlinear Convex Anal., 16(6):1147–1153, 2015
    Karim Adiprasito and Tudor Zamfirescu
  • Finitely forcible graphons and permutons. J. Combin. Theory Ser. B, 110:112–135, 2015
    R. Glebov, A. Grzesik, T. Klimošová, and D. Král’
  • Fixed-parameter complexity and approximability of norm maximization. Discrete & Computational Geometry, 53(2):276–295, 2015
    Christian Knauer, Stefan König, and Daniel Werner
  • Higher chordality: From graphs to complexes. 2015. Proceedings of the American Mathematical Society
    Karim Adiprasito, Eran Nevo, and Jose Samper
  • Highly linked tournaments. J. Combin. Theory B, 115:339–347, 2015
    A. Pokrovskiy
  • Identifying codes and searching with balls in graphs. Discrete Appl. Math., 193:39–47, 2015
    Y. Kim, M. Kumbhat, Z. Nagy, B. Patkós, A. Pokrovskiy, and M. Vizer
  • Keeping Avoider’s graph almost acyclic. Electronic Journal of Combinatorics, 22(1), 2015
    D. Clemens, J. Ehrenmuller, Y. Person, and T. Tran
  • Large-scale election campaigns: Combinatorial shift bribery. In Proceedings of the 2015 International Conference on Autonomous Agents and Multiagent Systems (AAMAS ’15), pages 67–75. ACM, 2015
    Robert Bredereck, Piotr Faliszewski, Rolf Niedermeier, and Nimrod Talmon
  • Lorentzian Coxeter systems and Boyd–Maxwell ball packings. Geom. Dedicata, 174:43–73, 2015
    Hao Chen and Jean-Philippe Labbé
  • Lp-based approximation algorithms for facility location in buy-at-bulk network design. In WADS, volume 9214 of Lecture Notes in Computer Science, pages 373–385. Springer, 2015
    Zachary Friggstad, Mohsen Rezapour, Mohammad R. Salavatipour, and José A. Soto
  • Many non-equivalent realizations of the associahedron. Combinatorica, 35(5):513–551, 2015
    Cesar Ceballos, Francisco Santos, and Günter M. Ziegler
  • Many projectively unique polytopes. Invent. Math., 199(3):581–652, 2015
    Karim Adiprasito and Günter Ziegler
  • Multi-player diffusion games on graph classes. In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC ’15), volume 9076 of LNCS, pages 200–211. Springer, 2015
    Laurent Bulteau, Vincent Froese, and Nimrod Talmon
  • Network Design with Facility Location: Approximation and Exact Techniques. PhD thesis, Technical University Berlin, 2015
    Mohsen Rezapour
  • On k-level matroids: geometry and combinatorics. PhD thesis, Free University Berlin, 2015
    Francesco Grande
  • On Problems in Extremal Combinatorics. PhD thesis, Free University Berlin, 2015
    T. Tran
  • On the concentration of the domination number of the random graph. SIAM J. Discrete Math., 29(3):1186–1206, 2015
    Roman Glebov, Anita Liebenau, and Tibor Szabó
  • On the concentration of the domination number of the random graph. SIAM J. Discrete Math., 29:1186–1206, 2015
    R. Glebov, A. Liebenau, and T. Szabó
  • On the connectivity waiter-client game, October 2015
    Sylwia Antoniuk, Codrut Grosu, and Lothar Narins
  • Packing segments in a simple polygon is apx-hard. In Abstracts 31th European Workshop on Computational Geometry (EuroCG), 2015
    Heuna Kim and Tillmann Miltzow
  • Privacy in elections: k-anonymizing preference orders. In Proceedings of the International Symposium on Fundamentals of Computation Theory (FCT ’15), volume 9210 of LNCS, pages 299–310. Springer, 2015
    Nimrod Talmon
  • Realizability and inscribability for some simplicial spheres and matroid polytopes. 25 pages, 2015
    Moritz Firsching
  • Robust randomized matchings. In SODA, pages 1904– 1915. SIAM, 2015
    Jannik Matuschke, Martin Skutella, and José A. Soto
  • Routing games with progressive filling. IEEE Transactions on Networking, Volume: 24 Issue: 4, 2553 - 2562
    Tobias Harks, Martin Hoefer, Kevin Schewior, and Alexander Skopalik
  • The complexity of degree anonymization by graph contractions. In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC ’15), volume 9076 of LNCS, pages 260–271. Springer, 2015
    Sepp Hartung and Nimrod Talmon
  • The complexity of finding effectors. In Proceedings of the 12th Annual Conference on Theory and Applications of Models of Computation (TAMC ’15), volume 9076 of LNCS, pages 224–235. Springer, 2015
    Laurent Bulteau, Stefan Fafianie, Vincent Froese, Rolf Niedermeier, and Nimrod Talmon
  • The Dimension of Posets with Planar Cover Graphs. Graphs Combin., 31(4):927–939, 2015
    Stefan Felsner, William T. Trotter, and Veit Wiechert
  • The number of combinatorially different convex hulls of points in lines. In Abstracts 31th European Workshop on Computational Geometry (EuroCG), 2015
    Heuna Kim, Wolfgang Mulzer, and Eunjin Oh
  • The Random Graph Intuition for the Tournament Game. Combinator. Probab. Comp., 25(01):76–88, sep 2015
    Dennis Clemens, Heidi Gebauer, and Anita Liebenau
  • The shadows of a cycle cannot all be paths. In Proceedings of the 27th Canadian Conference on Computational Geometry (CCCG), pages 70–75, 2015
    Prosenjit K. Bose, Jean-Lou De Carufel, Michael Gene Dobbins, Heuna Kim, and Giovanni Viglietta
  • Tight complexes in 3-space admit perfect discrete Morse functions. Eur. J. Comb., 45:71–84, 2015
    Karim Adiprasito and Bruno Benedetti
  • Time-space trade-offs for triangulations and Voronoi diagrams. In Algorithms and Data Structures, volume 9214 of Lecture Notes in Computer Science, pages 482–494. Springer International Publishing, 2015
    Matias Korman, Wolfgang Mulzer, André van Renssen, Marcel Roeloffzen, Paul Seiferth, and Yannik Stein
  • Universality theorems for inscribed polytopes and Delaunay triangulations. Discrete Comput. Geom., 54(2):412–431, 2015
    Karim Adiprasito, Arnau Padrol, and Louis Theran
  • A Geometric Lower Bound Theorem. 2016. Geometric and Functional Analysis
    Karim Adiprasito, Eran Nevo, and Jose Samper
  • A universality theorem for projectively unique polytopes and a conjecture of Shephard. Isr. J. Math., (2016) 211: 239
    Karim Adiprasito and Arnau Padrol
  • Almost all trees are almost graceful
    Anna Adamaszek, Peter Allen, Codrut Grosu, Jan Hladky
  • Intersection Graphs and Geometric Objects in the Plane. PhD thesis, Technical University Berlin, 2016
    Udo Hoffmann
  • NP-hardness of two edge cover generalizations with applications to control and bribery for approval voting. Information Processing Letters, 116, Issue 2, February 2016, Pages 147-152
    Robert Bredereck and Nimrod Talmon
  • On the maximum number of latin transversals. Journal of Combinatorial Theory, Series A, Volume 141, July 2016, Pages 136-146
    R. Glebov and Z. Luria
  • Optimization Methods in Discrete Geometry. PhD thesis, Free University Berlin, 2016
    Moritz Firsching
  • Relative Stanley–Reisner Theory and Upper Bound Theorems for Minkowski sums. 2016. Publications Mathematiques de l’IHÉS
    Karim Adiprasito and Raman Sanyal
  • Shadows of a closed curve. Submitted to 32nd International Symposium on Computational Geometry (SoCG 2016), 2016
    Michael Gene Dobbins, Heuna Kim, Luis Montejano, and Edgardo Roldán-Pensado
  • Sparsity and dimension. In Proceedings of the Twenty-Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, pages 1804–1813, 2016
    Gwenaël Joret, Piotr Micek, and Veit Wiechert
  • The diameter of type D associahedra and the non-leaving-face property. European Journal of Combinatorics, 51:109–124, January 2016
    Cesar Ceballos and Vincent Pilaud
  • Three ways to cover a graph. Discrete Mathematics, 339(2):745–758, 2016
    Kolja B. Knauer and Torsten Ueckerdt
  • Powers of Hamilton cycles in pseudo-random graphs. Combinatorica (2017) 37: 573
    P. Allen, J. Böttcher, H. Hàn, Y. Kohayakawa, and Y. Person
  • Subdivisions, shellability, and collapsibility of products. Combinatorica (2017) 37: 1
    Karim Adiprasito and Bruno Benedetti
  • The number of hamiltonian decompositions of regular graphs. Isr. J. Math. (2017) 222: 91
    R. Glebov, Z. Luria, and B. Sudakov
  • The threshold probability for long cycles. Combinatorics, Probability and Computing, 26, Issue 2 March 2017 , pp. 208-247
    R. Glebov, H. Naves, and B. Sudakov
  • The universality theorem for neighborly polytopes. Combinatorica, (2017) 37: 129
    Karim Adiprasito and Arnau Padrol
  • Combinatorial positivity of translation-invariant valuations and a discrete Hadwiger theorem. Journal of the European Mathematical Society, 20.9
    Katharina Jochemko and Raman Sanyal
  • Infinite dimensional finitely forcible graphon
    R. Glebov, T. Klimošová, and D. Král’
 
 

Zusatzinformationen

Textvergrößerung und Kontrastanpassung