| 2012 | Survivable Network Activation Problems. | Zeev Nutov |
| 2012 | Degree-Constrained Node-Connectivity. | Zeev Nutov |
| 2012 | Fully Analyzing an Algebraic Plya Urn Model. | Basile Morcrette |
| 2012 | The Feedback Arc Set Problem with Triangle Inequality Is a Vertex Cover Problem. | Monaldo Mastrolilli |
| 2012 | Random Walks and Bisections in Random Circulant Graphs. | Bernard Mans, Igor E. Shparlinski |
| 2012 | Oblivious Two-Way Finite Automata: Decidability and Complexity. | Martin Kutrib, Andreas Malcher, Giovanni Pighizzini |
| 2012 | Independence of Tabulation-Based Hash Classes. | Toryn Qwyllyn Klassen, Philipp Woelfel |
| 2012 | Advantage of Overlapping Clusters for Minimizing Conductance. | Rohit Khandekar, Guy Kortsarz, Vahab S. Mirrokni |
| 2012 | On the Performance of Smith's Rule in Single-Machine Scheduling with Nonlinear Cost. | Wiebke Hhn, Tobias Jacobs |
| 2012 | Hiring above the m-th Best Candidate: A Generalization of Records in Permutations. | Ahmed Helmi, Conrado Martnez, Alois Panholzer |
| 2012 | On the Bend-Number of Planar and Outerplanar Graphs. | Daniel Heldt, Kolja B. Knauer, Torsten Ueckerdt |
| 2012 | Algorithms for Some H-Join Decompositions. | Michel Habib, Antoine Mamcarz, Fabien de Montgolfier |
| 2012 | The Efficiency of MapReduce in Parallel External Memory. | Gero Greiner, Riko Jacob |
| 2012 | Cache Me If You Can: Capacitated Selfish Replication Games. | Ragavendran Gopalakrishnan, Dimitrios Kanoulas, Naga Naresh Karuturi, C. Pandu Rangan, Rajmohan Rajaraman, Ravi Sundaram |
| 2012 | New Lower Bound on Max Cut of Hypergraphs with an Application to r -Set Splitting. | Archontia C. Giannopoulou, Sudeshna Kolay, Saket Saurabh |
| 2012 | Indexed Multi-pattern Matching. | Travis Gagie, Kalle Karhu, Juha Krkkinen, Veli Mkinen, Leena Salmela, Jorma Tarhio |
| 2012 | Efficient Arbitrary and Resolution Proofs of Unsatisfiability for Restricted Tree-Width. | Martin Frer |
| 2012 | NE Is Not NP Turing Reducible to Nonexponentially Dense NP Sets. | Bin Fu |
| 2012 | Decidability Classes for Mobile Agents Computing. | Pierre Fraigniaud, Andrzej Pelc |
| 2012 | k-Gap Interval Graphs. | Fedor V. Fomin, Serge Gaspers, Petr A. Golovach, Karol Suchan, Stefan Szeider, Erik Jan van Leeuwen, Martin Vatshelle, Yngve Villanger |
| 2012 | Structural Complexity of Multiobjective NP Search Problems. | Krzysztof Fleszar, Christian Glaer, Fabian Lipp, Christian Reitwiener, Maximilian Witek |
| 2012 | Forbidden Patterns. | Johannes Fischer, Travis Gagie, Tsvi Kopelowitz, Moshe Lewenstein, Veli Mkinen, Leena Salmela, Niko Vlimki |
| 2012 | Clique-Colouring and Biclique-Colouring Unichord-Free Graphs. | Hlio B. Macdo Filho, Raphael C. S. Machado, Celina M. H. de Figueiredo |
| 2012 | On the Non-progressive Spread of Influence through Social Networks. | MohammadAmin Fazli, Mohammad Ghodsi, Jafar Habibi, Pooya Jalaly Khalilabadi, Vahab S. Mirrokni, Sina Sadeghian Sadeghabad |
| 2012 | Opportunistic Information Dissemination in Mobile Ad-Hoc Networks: Adaptiveness vs. Obliviousness and Randomization vs. Determinism. | Martin Farach-Colton, Antonio Fernndez Anta, Alessia Milani, Miguel A. Mosteiro, Shmuel Zaks |