Database Entry Point
max planck institut
informatik
mpii logo Minerva of the Max Planck Society
 

MPI-INF D1 Publications , MPG Format, generated: Tuesday, 2. September 2014

Scientific Publications for 2012

Abed, F. and C.-C. Huang: Preemptive coordination mechanisms for unrelated machines. In: Algorithms - ESA 2012 : 20th Annual European Symp., Lect. Notes Comput. Sci. 7501, (Eds.) L. Epstein, P. Ferragina. Springer, Berlin 2012, 12-23.

Agrawal, M., C. Saha, R. Saptharishi and N. Saxena: Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits. In: STOC'12 : Proc. 2012 ACM Symp. on Theory of Computing. ACM, New York 2012, 599-614.

Ailon, N., N. Avigdor-Elgrabli, E. Liberty and A. van Zuylen: Improved approximation algorithms for bipartite correlation clustering. SIAM Journal on Computing 41, 1110-1121 (2012).

Ajwani, D., K. Elbassioni, S. Govindarajan and S. Ray: Conflict-free coloring for rectangle ranges using o(n .382) colors. Discrete & Computational Geometry 48, 39-52 (2012).

Akbari, H., P. Berenbrink and T. Sauerwald: A simple approach for adapting continuous load balancing processes to discrete settings. In: PODC'12 : Proc. 2012 ACM Symp. on Principles of Distributed Computing, (Eds.) D. Kowalski, A. Panconesi. ACM, New York 2012, 271-280.

Alcaraz, N., T. Friedrich, T. Kötzing, A. Krohmer, J. Müller, J. Pauling and J. Baumbach: Efficient key pathway mining: combining networks and OMICS data. Integrative Biology 4, 756-764 (2012).

Alvarez, V., K. Bringmann, R. Curticapean and S. Ray: Counting crossing free structures. In: Proc. Twenty-Eight Annual Symp. on Computational Geometry (SCG'12), (Eds.) T.K. Dey, S. Whitesides. ACM, New York 2012, 61-68.

Baruah, S., V. Bonifaci, G. D'Angelo, H. Li, A. Marchetti-Spaccamela, N. Megow and L. Stougie: Scheduling real-time mixed-criticality jobs. IEEE Transactions on Computers 61, 1140-1152 (2012).

Baumbach, J., T. Friedrich, T. Kötzing, A. Krohmer, J. Müller and J. Pauling: Efficient algorithms for extracting biological key pathways with global constraints. In: GECCO'12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation. ACM, New York 2012, 169-176.

Belfrage, M., T. Mütze and R. Spöhel: Probabilistic one-player Ramsey games via deterministic two-player games. SIAM Journal on Discrete Mathematics 26, 1031-1049 (2012).

Berberich, E., D. Halperin, M. Kerber and R. Pogalnikova: Deconstructing approximate offsets. Discrete & Computational Geometry 48, 964-989 (2012).

Bonifaci, V., H.-L. Chan, A. Marchetti-Spaccamela and N. Megow: Algorithms and complexity for periodic real-time scheduling. ACM Transactions on Algorithms 9, 601-619 (2012).

Bonifaci, V. and A. Marchetti-Spaccamela: Feasibility analysis of sporadic real-time multiprocessor task systems. Algorithmica 63, 763-780 (2012).

Bonifaci, V., A. Marchetti-Spaccamela and S. Stiller: A constant-approximate feasibility test for multiprocessor real-time scheduling. Algorithmica 62, 1034-1049 (2012).

Bonifaci, V., K. Mehlhorn and G. Varma: Physarum can compute shortest paths. Journal of Theoretical Biology 309, 121-133 (2012).

- Physarum can compute shortest paths. In: Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-12), (Ed.) Y. Ravani. SIAM, Philadelphia 2012, 233-240.

Boros, E., K. Elbassioni, V. Gurvich and K. Makino: On Nash equilibria and improvement cycles in pure positional strategies for Chess-like and Backgammon-like n-person games. Discrete Mathematics 312, 772-788 (2012).

Brightwell, G., K. Panagiotou and A. Steger: Extremal subgraphs of random graphs. Random Structures & Algorithms 41, 147-178 (2012).

Bringmann, K.: An improved algorithm for Klee's measure problem on fat boxes. Computational Geometry: Theory and Applications 45, 225-233 (2012).

Bringmann, K. and T. Friedrich: Approximating the least hypervolume contributor: NP-hard in general, but fast in practice. Theoretical Computer Science 425, 104-116 (2012).

- Convergence of hypervolume-based archiving algorithms II: competitiveness. In: GECCO'12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation. ACM, New York 2012, 457-464.

Bringmann, K. and K. Panagiotou: Efficient sampling methods for discrete distributions. In: Automata, Languages, and Programming : 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7391, (Eds.) A. Czumaj, K. Mehlhorn, A.M. Pitts, R. Wattenhofer. Springer, Berlin 2012, 133-144.

Canzar, S., M. El-Kebir, R. Pool, K. Elbassioni, A.K. Malde, A.E. Mark, D.P. Geerke, L. Stougie and G.W. Klau: Charge group partitioning in biomolecular simulation. In: Research in Computational Molecular Biology : 16th Annual Int. Conf., RECOMB 2012, Lecture Notes in Bioinformatics 7262, (Ed.) B. Chor. Springer, Berlin 2012, 29-43.

Case, J. and T. Kötzing: Computability-theoretic learning complexity. Philosophical Transaction of the Royal Society A 370, 3570-3596 (2012).

- Learning secrets interactively. Dynamic modeling in inductive inference. Information and Computation 220-221, 60-73 (2012).

Chan, H.-L., T.-W. Lam, L.-K. Lee and H.-F. Ting: Continuous monitoring of distributed data streams over a time-based sliding window. Algorithmica 62, 1088-1111 (2012).

Chan, H.-L., N. Megow, R. Sitters and R. van Stee: A note on sorting buffers offline. Theoretical Computer Science 423, 11-18 (2012).

Chen, X., B. Doerr, X. Hu, W. Ma, R. van Stee and C. Winzen: The price of anarchy for selfish ring routing is two. In: Internet and Network Economics : 8th Int. Workshop, WINE 2012, Lect. Notes Comput. Sci. 7695, (Ed.) P.W. Goldberg. Springer, Berlin 2012, 420-433.

Croitoru, C. and T. Kötzing: Deliberative acceptability of arguments. In: STAIRS 2012 - Proc. Sixth Starting AI Researchers' Symp., Frontiers in Artificial Intelligence and Applications 241, (Eds.) K. Kersting, M. Toussaint. IOS Press, Amsterdam 2012, 71-82.

Cygan, M., H. Dell, D. Lokshtanov, D. Marx, J. Nederlof, Y. Okamoto, R. Paturi, S. Saurabh and M. Wahlström: On problems as hard as CNF-SAT. In: 2012 IEEE 27th Conf. on Computational Complexity (CCC 2012). IEEE, Piscataway 2012, 74-84.

Cygan, M., S. Kratsch, M. Pilipczuk, M. Pilipczuk and M. Wahlström: Clique cover and graph separation: New incompressibility results. In: Automata, Languages, and Programming : 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7391, (Eds.) A. Czumaj, K. Mehlhorn, A.M. Pitts, R. Wattenhofer. Springer, Berlin 2012, 254-265.

De Sterck, H.: A nonlinear GMRES optimization algorithm for canonical tensor decomposition. SIAM Journal on Scientific Computing 34, A1351-A1379 (2012).

- A self-learning algebraic multigrid method for extremal singular triplets and eigenpairs. SIAM Journal on Scientific Computing 34, A2092-A2117 (2012).

Doerr, B.: Black-box complexity: from complexity theory to playing mastermind. In: GECCO'12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation, (Eds.) T. Soule, J.H. Moore. ACM, New York 2012, 1079-1092.

Doerr, B., M. Fouz and T. Friedrich: Asynchronous rumor spreading in preferential attachment graphs. In: Algorithm Theory - SWAT 2012 : 13th Scandinavian Symp. and Workshops, Lect. Notes Comput. Sci. 7357, (Eds.) F.V. Fomin, P. Kaski. Springer, Berlin 2012, 307-315.

- Experimental analysis of rumor spreading in social networks. In: Design and Analysis of Algorithms First Mediterranean Conf. on Algorithms, MedAlg 2012, Lect. Notes Comput. Sci. 7659, (Eds.) G. Even, D. Rawitz. Springer, Berlin 2012, 159-173.

- Why rumors spread fast in social networks. Communications of the ACM 55, 70-75 (2012).

Doerr, B., E. Happ and C. Klein: Crossover can provably be useful in evolutionary computation. Theoretical Computer Science 425, 17-33 (2012).

Doerr, B., A. Hota and T. Kötzing: Ants easily solve stochastic shortest path problems. In: GECCO'12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation, (Eds.) T. Soule, J.H. Moore. ACM, New York 2012, 17-24.

Doerr, B., D. Johannsen and C. Winzen: Multiplicative drift analysis. Algorithmica 64, 673-697 (2012).

- Non-existence of linear universal drift functions. Theoretical Computer Science 436, 71-86 (2012).

Doerr, B. and S. Pohl: Run-time analysis of the (1+1) evolutionary algorithm optimizing linear functions over a finite alphabet. In: GECCO'12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation, (Eds.) T. Soule, J.H. Moore. ACM, New York 2012, 1317-1324.

Doerr, B., R. Spöhel, H. Thomas and C. Winzen: Playing mastermind with many colors. In: Proc. of the 11th Cologne-Twente Workshop on Graphs and Combinatorial Optimization (CTW 2012) [***Warning: Editor(s) might be missing!]. 0, 0 2012, [***Warning: Pages missing!].

Doerr, B. and C. Winzen: Black-box complexity: Breaking the O(n logn) barrier of LeadingOnes. In: Artificial Evolution 10th Int. Conf. Evolution Artificielle, EA 2011, Lect. Notes Comput. Sci. 7401, (Eds.) J.-K. Hao, P. Legrand, P. Collet, N. Monmarché, E. Lutton, M. Schoenauer. Springer, Berlin 2012, 205-216.

- Memory-restricted black-box complexity of OneMax. Information Processing Letters 112, 32-34 (2012).

- Reducing the arity in unbiased black-box complexity. In: GECCO'12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation, (Eds.) T. Soule, J.H. Moore. ACM, New York 2012, 1309-1316.

Elbassioni, K.: A QPTAS for ε-envy-free profit-maximizing pricing on line graphs. In: Automata, Languages, and Programming : 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7392, (Eds.) A. Czumaj, K. Mehlhorn, A.M. Pitts, R. Wattenhofer. Springer, Berlin 2012, 513-524.

Elbassioni, K., M. Fouad and E. Bertino: Modeling the risk & utility of information sharing in social networks. In: 2012 ASE/IEEE Int. Conf. on Privacy, Security, Risk and Trust and 2012 ASE/IEEE Int. Conf. on Social Computing : SocialCom/PASSAT 2012. IEEE, Piscataway 2012, 441-450.

Elbassioni, K., S. Jeli´c and D. Matijevi`c: The relation of connected set cover and group Steiner tree. Theoretical Computer Science 438, 96-101 (2012).

Elbassioni, K., D. Matijevic and D. Severdija: Guarding 1.5D terrains with demands. International Journal of Computer Mathematics 89, 2143-2151 (2012).

Elbassioni, K., R. Raman, S. Ray and R. Sitters: On the complexity of the highway problem. Theoretical Computer Science 460, 70-77 (2012).

Elbassioni, K. and H.R. Tiwary: Complexity of approximating the vertex centroid of a polyhedron. Theoretical Computer Science 421, 56-61 (2012).

Elmasry, A., K. Mehlhorn and J.M. Schmidt: An O(n+m) certifying triconnnectivity algorithm for Hamiltonian graphs. Algorithmica 62, 754-766 (2012).

Emeliyanenko, P. and M. Sagraloff: On the complexity of solving a bivariate polynomial system. In: ISSAC 2012 : Proc. 37th Int. Symp. on Symbolic and Algebraic Computation, (Eds.) J. van der Hoeven, M. van Hoeij. ACM, New York 2012, 154-161.

Epstein, L., L. Jez, J. Sgall and R. van Stee: Online scheduling of jobs with fixed start times on related machines. In: Approximation, Randomization, and Combinatorial Optimization : Algorithms and Techniques ; 15th Int. Workshop, APPROX 2012 and 16th Int. Workshop, RANDOM 2012, Lect. Notes Comput. Sci. 7408, (Eds.) A. Gupta, K. Jansen, J. Rolim, R. Servedio. Springer, Berlin 2012, 134-145.

Epstein, L., A. Levin, A. Marchetti-Spaccamela, N. Megow, J. Mestre, M. Skutella and L. Stougie: Universal sequencing on an unreliable machine. SIAM Journal on Computing 41, 565-586 (2012).

Epstein, L., A. Levin and R. van Stee: Approximation schemes for packing splittable items with cardinality constraints. Algorithmica 62, 102-129 (2012).

Epstein, L. and R. van Stee: The price of anarchy on uniformly related machines revisited. Information and Computation 212, 37-54 (2012).

Fellows, M.R., D. Hermelin and F.A. Rosamond: Well quasi orders in subclasses of bounded treewidth graphs and their algorithmic applications. Algorithmica 64, 3-18 (2012).

Fountoulakis, N. and K. Panagiotou: Tight load thresholds for cuckoo hashing. Random Structures and Algorithms 41, 306-333 (2012).

Fountoulakis, N., K. Panagiotou and T. Sauerwald: Ultra-fast rumor spreading in social networks. In: Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-12), (Ed.) Y. Rabani. SIAM, Philadelphia 2012, 1642-1660.

Friedrich, T., M. Gairing and T. Sauerwald: Quasirandom load balancing. SIAM Journal on Computing 41, 747-771 (2012).

Gawrychowski, P.: Faster algorithm for computing the edit distance between SLP-Compressed strings. In: String Processing and Information Retrieval : 19th Int. Symp., SPIRE 2012, Lect. Notes Comput. Sci. 7608, (Eds.) L. Calderón-Benavides, C.N. González-Caro, E. Chávez, N. Ziviani. Springer, Berlin 2012, 229-236.

- Simple and efficient LZW-compressed multiple pattern matching. In: Combinatorial Pattern Matching : 23rd Annual Symp., CPM 2012, Lect. Notes Comput. Sci. 7354, (Eds.) J. Kärkkäinen, J. Stoye. Springer, Berlin 2012, 232-242.

Giakkoupis, G. and T. Sauerwald: Rumor spreading and vertex expansion. In: Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-12), (Ed.) Y. Rabani. SIAM, Philadelphia 2012, 1623-1641.

Giannopoulos, P., C. Knauer, M. Wahlström and D. Werner: Hardness of discrepancy computation and ε-net verification in high dimension. Journal of Complexity 28, 162-176 (2012).

Gnewuch, M., M. Wahlström and C. Winzen: A new randomized algorithm to approximate the star discrepancy based on threshold accepting. SIAM Journal on Numerical Analysis 50, 781-807 (2012).

Harren, R. and W. Kern: Improved lower bound for online strip packing. In: Approximation and Online Algorithms : 9th Int. Workshop ,WAOA 2011, Lect. Notes Comput. Sci. 7164, (Eds.) R. Solis-Oba, G. Persiano. Springer, Berlin 2012, 211-218.

Harren, R. and R. van Stee: Absolute approximation ratios for packing rectangles into bins. Journal of Scheduling 15, 63-75 (2012).

Heinz, J., A. Kasprzik and T. Kötzing: Learning in the limit with lattice-structured hypothesis spaces. Theoretical Computer Science 457, 111 - 127 (2012).

Hermelin, D., J. Mestre and D. Rawitz: Optimization problems in dotted interval graphs. In: Graph-Theoretic Concepts in Computer Science : 38th Int.Workshop, WG 2012, Lect. Notes Comput. Sci. 7551, (Eds.) M.C. Golumbic, M. Stern, A. Levy, G. Morgenstern. Springer, Berlin 2012, 46-56.

Hermelin, D., M. Mnich and E.J. van Leeuwen: Parameterized complexity of induced H-matching on claw-free graphs. In: Algorithms - ESA 2012 : 20th Annual European Symp., Lect. Notes Comput. Sci. 7501, (Eds.) L. Epstein, P. Ferragina. Springer, Berlin 2012, 624-635.

Hermelin, D., R. Rizzi and S. Vialette: Algorithmic aspects of the intersection and overlap numbers of a graph. In: Algorithms and Computation : 23rd Int. Symp., ISAAC 2012, Lect. Notes Comput. Sci. 7676, (Eds.) K.-M. Chao, T.-s. Hsu, D.-T. Lee. Springer, Berlin 2012, 465-474.

Hermelin, D. and X. Wu: Weak compositions and their applications to polynomial lower bounds for kernelization. In: Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-12), (Ed.) Y. Rabani. SIAM, Philadelphia 2012, 104-113.

Höhn, W., T. Jacobs and N. Megow: On Eulerian extensions and their application to no-wait flowshop scheduling. Journal of Scheduling 15, 295-309 (2012).

Jain, S., T. Kötzing and F. Stephan: Enlarging learnable classes. In: Algorithmic Learning Theory : 23rd Int. Conf., ALT 2012, Lect. Notes Artif. Intell. 7568, (Eds.) N. Bshouty, G. Stoltz, N. Vayatis, T. Zeugmann. Springer, Berlin 2012, 36-50.

Kane, D., K. Mehlhorn, T. Sauerwald and H. Sun: Counting arbitrary subgraphs in data streams. In: Automata, Languages, and Programming : 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7392, (Eds.) A. Czumaj, K. Mehlhorn, A.M. Pitts, R. Wattenhofer. Springer, Berlin 2012, 598-609.

Kavitha, T. and J. Mestre: Max-coloring paths: tight bounds and extensions. Journal of Combinatiorial Optimization 24, 1-14 (2012).

Kayal, N. and C. Saha: On the sum of square roots of polynomials and related problems. The ACM Transactions on Computation Theory 4, 9:1-9:15 (2012).

Kerber, M. and M. Sagraloff: A worst-case bound for topology computation of algebraic curves. Journal of Symbolic Computation 47, 239-258 (2012).

Kim, E.J., C. Paul and G. Philip: A single-exponential FPT algorithm for the K4-Minor cover problem. In: Algorithm Theory - SWAT 2012 : 13th Scandinavian Symp. and Workshops, Lect. Notes Comput. Sci. 7357, (Eds.) F.V. Fomin, P. Kaski. Springer, Berlin 2012, 119-130.

Knauer, C., L. Schlipf, J.M. Schmidt and H.R. Tiwary: Largest inscribed rectangles in convex polygons. Journal of Discrete Algorithms 13, 78-85 (2012).

Kötzing, T. and H. Molter: ACO beats EA on a dynamic pseudo-Boolean function. In: Parallel Problem Solving from Nature - PPSN XII : 12th Int. Conf., Lect. Notes Comput. Sci. 7491, (Eds.) C.A. Coello Coello, V. Cutello, K. Deb, S. Forrest, G. Nicosia, M. Pavone. Springer, Berlin 2012, 113-122.

Kötzing, T., F. Neumann, H. Röglin and C. Witt: Theoretical analysis of two ACO approaches for the traveling salesman problem. Swarm Intelligence 6, 1-21 (2012).

Kötzing, T., A.M. Sutton, F. Neumann and U.-M. O'Reilly: The max problem revisited: the importance of mutation in genetic programming. In: GECCO’12 : Proc. Fourteenth Int. Conf. on Genetic and Evolutionary Computation, (Eds.) T. Soule, J.H. Moore. ACM, New York 2012, 1333-1340.

Kratsch, S., M. Pilipczuk, M. Pilipczuk and M. Wahlström: Fixed-Parameter tractability of multicut in directed acyclic graphs. In: Automata, Languages, and Programming ; 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7391, (Eds.) A. Czumaj, K. Mehlhorn, A.M. Pitts, R. Wattenhofer. Springer, Berlin 2012, 581-593.

Kratsch, S. and M. Wahlström: Compression via matroids: a randomized polynomial kernel for odd cycle transversal. In: Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-12), (Ed.) Y. Rabani. SIAM, Philadelphia 2012, 94-103.

- Representative sets and irrelevant vertices: new tools for kernelization. In: IEEE 53rd Annual Symp. on Foundations of Computer Science (FOCS-12), (Ed.) T. Roughgarden. IEEE Computer Society, Los Alamitos 2012, 450-459.

Krivelevich, M. and R. Spöhel: Creating small subgraphs in Achlioptas processes with growing parameter. SIAM Journal on Discrete Mathematics 26, 670-686 (2012).

Megow, N., K. Mehlhorn and P. Schweitzer: Online graph exploration: new results on old and new algorithms. Theoretical Computer Science 463, 62-72 (2012).

Megow, N., M. Skutella, J. Verschae and A. Wiese: The power of recourse for online MST and TSP. In: Automata, Languages, and Programming : 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7391, (Eds.) A. Czumaj, K. Mehlhorn, A.M. Pitts, R. Wattenhofer. Springer, Berlin 2012, 689-700.

Meyerhenke, H. and T. Sauerwald: Beyond good partition shapes: an analysis of diffusive graph partitioning. Algorithmica 64, 329-361 (2012).

Misra, N., G. Philip, V. Raman and S. Saurabh: On parameterized independent feedback vertex set. Theoretical Computer Science 461, 65-75 (2012).

Misra, N., G. Philip, V. Raman, S. Saurabh and S. Sikdar: FPT algorithms for connected feedback vertex set. Journal of Combinatorial Optimization 24, 131-146 (2012).

Nor, I., D. Hermlin, S. Charlat, J. Engelstadter, M. Reuter, O. Duron and M.-F. Sagot: Mod/Resc parsimony inference: theory and application. Information and Computation 213, 23-32 (2012).

Panagiotou, K. and A. Coja-Oghlan: Catching the k-NAESAT threshold. In: STOC’12 : Proc. 2012 ACM Symp. on Theory of Computing. ACM, New York 2012, 899-907.

Panagiotou, K. and M. Sinha: Vertices of degree k in random unlabeled trees. Journal of Graph Theory 69, 114-130 (2012).

Philip, G., V. Raman and S. Sikdar: Polynomial kernels for dominating set in graphs of bounded degeneracy and beyond. ACM Transactions on Algorithms 9, 23 (2012).

Qian, J., F. Schalekamp, D.P. Williamson and A. van Zuylen: On the integrality gap of the subtour LP for the 1,2-TSP. In: LATIN 2012: Theoretical Informatics ; 10th Latin American Symp., Lect. Notes Comput. Sci. 7256, (Ed.) D. Fernández-Baca. Springer, Berlin 2012, 606-617.

Sagraloff, M.: When Newton meets Descartes: A simple and fast algorithm to isolate the real roots of a polynomial. In: ISSAC 2012 : Proc. 37th Int. Symp. on Symbolic and Algebraic Computation, (Eds.) J. van der Hoeven, M. van Hoeij. ACM, New York 2012, 297-304.

Sauerwald, T. and H. Sun: Tight bounds for randomized load balancing on arbitrary network topologies. In: IEEE 53rd Annual Symp. on Foundations of Computer Science (FOCS-12), (Ed.) T. Roughgarden. IEEE Computer Society, Los Alamitos 2012, 341-350.

Schalekamp, F., D.P. Williamson and A. van Zuylen: A proof of the Boyd-Carr conjecture. In: Proc. Twenty-Third Annual ACM-SIAM Symp. on Discrete Algorithms (SODA-12), (Ed.) Y. Rabani. SIAM, Philadelphia 2012, 1477-1486.

Schmidt, J.M.: Certifying 3-connectivity in linear time. In: Automata, Languages, and Programming : 39th Int. Colloquium, ICALP 2012, Lect. Notes Comput. Sci. 7391, (Eds.) A. Czumaj, K. Mehlhorn, A. Pitts, R. Wattenhofer. Springer, Berlin 2012, 786-797.

- Construction sequences and certifying 3-connectivity. Algorithmica 62, 192-208 (2012).

Schmidt, J.M. and P. Valtr: Cubic plane graphs on a given point set. In: Proc. Twenty-Eighth Annual Symp. on Computational Geometry (SCG'12). ACM, New York 2012, 201-208.

Soranzo, N., F. Ramezani, G. Iacono and C. Altafini: Decompositions of large-scale biological systems based on dynamical properties. Bioinformatics 28, 76-83 (2012).

van Stee, R.: An improved algorithm for online rectangle filling. Theoretical Computer Science 423, 59-74 (2012).

- SIGACT News online algorithms column 20: the power of harmony. SIGACT News 43, 127-136 (2012).

- SIGACT News online algorithms column 21: APPROX and ALGO. SIGACT News 43, 123-129 (2012).

van Zuylen, A.: Simpler 3/4-approximation algorithms for MAX SAT. In: Approximation and Online Algorithms : 9th Int. Workshop, WAOA 2011, Lect. Notes Comput. Sci. 7164, (Eds.) R. Solis-Oba, P. Persiano. Springer, Berlin 2012, 188-197.

Publikationen im Internet

Afshani, P., M. Agrawal, B. Doerr, K. Green Larsen, K. Mehlhorn and C. Winzen: The query complexity of finding a hidden permutation. Electronic Colloquium on Computational Complexity (ECCC): Report Series 87 (Revision 1), 1-36 (2012). Internet: <http://eccc.hpi-web.de/report/2012/087>

Agrawal, M., C. Saha and N. Saxena: Quasi-polynomial hitting-set for set-depth-delta formulas. arXiv abs/1209.2333, 1-13 (2012). Internet: <http://arxiv.org/abs/1209.2333>

Berberich, E., P. Emeliyanenko, A. Kobel and M. Sagraloff: Exact symbolic-numeric computation of planar algebraic curves. arXiv abs/1201.1548v1, 1-46 (2012). Internet: <http://arxiv.org/abs/1201.1548v1>

Doerr, B., S. Moran, S. Moran and C. Winzen: Simple and optimal fault-tolerant rumor spreading. arXiv abs/1209.6158, 1-18 (2012). Internet: <http://arxiv.org/abs/1209.6158>

Doerr, B. and C. Winzen: Playing Mastermind with constant-size memory. In: 29th Int. Symp. on Theoretical Aspects of Computer Science : STACS'12, (Eds.) C. Dürr, T. Wilke, LIPIcs 14. Schloss Dagstuhl/ Leibniz-Zentrum für Informatik, Dagstuhl 2012, 441-452 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3411/>.

- Playing Mastermind with constant-size memory. Theory of Computing Systems Online First, 1-27 (2012). Internet: <http://dx.doi.org/10.1007/s00224-012-9438-8>

Duan, R. and K. Mehlhorn: A combinatorial polynomial algorithm for the linear Arrow-Debreu market. arXiv abs/1212.0979v1, 1-8 (2012). Internet: <http://arxiv.org/abs/1212.0979>

Elbassioni, K., N. Garg, D. Gupta, A. Kumar, V. Narula and A. Pal: Approximation algorithms for the unsplittable flow problem on paths and trees. In: 32nd Int. Conf. on Foundations of Software Technology and Theoretical Computer Science : FSTTCS 2012, (Eds.) D. D'Souza, T. Kavitha, J. Radhakrishnan, LIPIcs 18. Schloß Dagstuhl/Leibniz Zentrum für Informatik, Dagstuhl 2012, 267-275 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3865/>.

Elbassioni, K., K. Paluch and A. van Zuylen: Simpler approximation of the maximum asymmetric traveling salesman problem. In: 29th Int. Symp. on Theoretical Aspects of Computer Science : STACS'12, (Eds.) C. Dürr, T. Wilke, LIPIcs 14. Schloss Dagstuhl/ Leibniz-Zentrum für Informatik, Dagstuhl 2012, 501-506 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3412/>.

Emeliyanenko, P.: Computing resultants on graphics processing units: Towards GPU-accelerated computer algebra. Journal of Parallel and Distributed Computing In press, 1-14 (2012). Internet: <http://dx.doi.org/10.1016/j.jpdc.2012.07.015>

Friedrich, T., T. Kroeger and F. Neumann: Weighted preferences in evolutionary multi-objective optimization. International Journal of Machine Learning and Cybernetics Online First, 1-10 (2012). Internet: <http://dx.doi.org/10.1007/s13042-012-0083-y>

Gawrychowski, P.: Tying up the loose ends in fully LZW-compressed pattern matching. In: 29th Int. Symp. on Theoretical Aspects of Computer Science : STACS'12, (Eds.) C. Dürr, T. Wilke, LIPIcs 14. Schloss Dagstuhl/ Leibniz-Zentrum für Informatik, Dagstuhl 2012, 624-635 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3397/>.

Giakkoupis, G., T. Sauerwald, H. Sun and P. Woelfel: Low randomness rumor spreading via hashing. In: 29th Int. Symp. on Theoretical Aspects of Computer Science : STACS'12, (Eds.) C. Dürr, T. Wilke, LIPIcs 14. Schloss Dagstuhl/ Leibniz-Zentrum für Informatik, Dagstuhl 2012, 314-325 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3441/>.

Lokshtanov, D., S. Saurabh and M. Wahlström: Subexponential parameterized odd cycle transversal on planar graphs. In: 32nd Int. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), (Eds.) D. D'Souza, T. Kavitha, J. Radhakrishna, LIPIcs 18. Schloss Dagstuhl/ Leibniz-Zentrum für Informatik, Dagstuhl 2012, 424-434 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3878/>.

Mnich, M., G. Philip, S. Saurabh and O. Suchy: Beyond max-cut: lambda-extendible properties parameterized above the Poljak-Turzík bound. In: 32nd Int. Conf. on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2012), (Eds.) D. D'Souza, T. Kavitha, J. Radhakrishnan, Leibniz International Proceedings in Informatics 18. Schloss Dagstuhl/ Leibniz-Zentrum für Informatik, Dagstuhl 2012, 412-423 Internet: <http://drops.dagstuhl.de/opus/volltexte/2012/3877/>.

Bachelor Thesis

Becker, R.: The Bolzano method to isolate the roots of a bitstream polynomial. Universität des Saarlandes 2012.

Feldmann, M.: Stochastic optimization with fitness proportional ant systems . Universität des Saarlandes 2012.

Heydrich, S.: Dividing connected chores fairly. Universität des Saarlandes 2012.

Master's thesis

Croitoru, C.: Algorithmic aspects of abstract argumentation frameworks. Universität des Saarlandes 2012.

Krohmer, A.: Finding cliques in scale-free networks. Universität des Saarlandes 2012.

Molter, H.: ACO beats EA on a dynamic pseudo-Boolean function. Universität des Saarlandes 2012.

Moran, S.: Shattering extremal systems. Universität des Saarlandes 2012.

Ott, S.: Thou shalt not lie : on truthfully maximizing the minimum load on selfish related machines. Universität des Saarlandes 2012.

Wang, P.: Certification of curve arrangements. Universität des Saarlandes 2012.

Doctoral dissertation

Emeliyanenko, P.: Harnessing the power of GPUs for problems in real algebraic geometry. Universität des Saarlandes 2012.

Fouz, M.: Randomized rumor spreading in social networks & complete graphs. Universität des Saarlandes 2012.