default search action
Algorithmica, Volume 83
Volume 83, Number 1, January 2021
- Junjie Luo, Hendrik Molter, André Nichterlein, Rolf Niedermeier:
Parameterized Dynamic Cluster Editing. 1-44 - Mong-Jen Kao:
Iterative Partial Rounding for Vertex Cover with Hard Capacities. 45-71 - Céline Chevalier, Fabien Laguillaumie, Damien Vergnaud:
Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions. 72-115 - Oswin Aichholzer, Jean Cardinal, Tony Huynh, Kolja Knauer, Torsten Mütze, Raphael Steiner, Birgit Vogtenhuber:
Flip Distances Between Graph Orientations. 116-143 - Jurek Czyzowicz, Dariusz Dereniowski, Andrzej Pelc:
Building a Nest by an Automaton. 144-176 - Amos Beimel, Kobbi Nissim, Uri Stemmer:
Learning Privately with Labeled and Unlabeled Examples. 177-215 - Maria Chudnovsky, Shenwei Huang, Sophie Spirkl, Mingxian Zhong:
List 3-Coloring Graphs with No Induced P6+rP3. 216-251 - Victor Chepoi, Arnaud Labourel, Sébastien Ratel:
Distance and Routing Labeling Schemes for Cube-Free Median Graphs. 252-296 - Robert Ganian, Fabian Klute, Sebastian Ordyniak:
On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem. 297-336 - Susanne Albers, Sebastian Schraink:
Tight Bounds for Online Coloring of Basic Graph Classes. 337-360 - Jeremy Kun, Michael P. O'Brien, Marcin Pilipczuk, Blair D. Sullivan:
Polynomial Treedepth Bounds in Linear Colorings. 361-386 - Sándor P. Fekete, Robert Gmyr, Sabrina Hugo, Phillip Keldenich, Christian Scheffer, Arne Schmidt:
CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata. 387-412
Volume 83, Number 2, February 2021
- Santanu Bhowmick, Tanmay Inamdar, Kasturi R. Varadarajan:
Fault-Tolerant Covering Problems in Metric Spaces. 413-446 - Vittorio Bilò, Marios Mavronicolas:
The Complexity of Computational Problems About Nash Equilibria in Symmetric Win-Lose Games. 447-530 - Angel A. Cantu, Austin Luchsinger, Robert T. Schweller, Tim Wylie:
Covert Computation in Self-Assembled Circuits. 531-552 - Zeev Nutov:
On the Tree Augmentation Problem. 553-575 - Ghurumuruhan Ganesan:
Constrained Minimum Passage Time in Random Geometric Graphs. 576-588 - Myriam Preissmann, Cléophée Robin, Nicolas Trotignon:
On the Complexity of Colouring Antiprismatic Graphs. 589-612 - Akira Matsubayashi:
Non-Greedy Online Steiner Trees on Outerplanar Graphs. 613-640 - Therese Biedl, Saeed Mehrabi:
On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth. 641-666 - Harry Buhrman, Matthias Christandl, Michal Koucký, Zvi Lotker, Boaz Patt-Shamir, Nikolai K. Vereshchagin:
High Entropy Random Selection Protocols. 667-694 - Diodato Ferraioli, Carmine Ventre:
Approximation Guarantee of OSP Mechanisms: The Case of Machine Scheduling and Facility Location. 695-725 - Robert Ganian, Sebastian Ordyniak:
The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths. 726-752 - Akanksha Agrawal, Fahad Panolan, Saket Saurabh, Meirav Zehavi:
Simultaneous Feedback Edge Set: A Parameterized Perspective. 753-774
Volume 83, Number 3, March 2021
- Zachary Friggstad, Jörg-Rüdiger Sack, Mohammad R. Salavatipour:
Special Issue on Algorithms and Data Structures (WADS 2019). 775 - Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo, Srinivasa Rao Satti:
Succinct Encodings for Families of Interval Graphs. 776-794 - Joan Boyar, Lene M. Favrholdt, Shahin Kamali, Kim S. Larsen:
Online Bin Covering with Advice. 795-821 - Marthe Bonamy, Nicolas Bousquet, Konrad K. Dabrowski, Matthew Johnson, Daniël Paulusma, Théo Pierron:
Graph Isomorphism for (H1, H2)-Free Graphs: An Almost Complete Dichotomy. 822-852 - Moran Feldman:
Guess Free Maximization of Submodular and Linear Sums. 853-878 - Chien-Chung Huang, Naonori Kakimura:
Improved Streaming Algorithms for Maximizing Monotone Submodular Functions under a Knapsack Constraint. 879-902
Volume 83, Number 4, April 2021
- Anne Auger, Per Kristian Lehre:
Preface to the Special Issue on Theory of Genetic and Evolutionary Computation. 903-905 - Feng Shi, Frank Neumann, Jianxin Wang:
Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem. 906-939 - Chao Qian, Chao Bian, Yang Yu, Ke Tang, Xin Yao:
Analysis of Noisy Evolutionary Optimization When Sampling Fails. 940-975 - Dirk Sudholt:
Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial. 976-1011 - Benjamin Doerr, Carsten Witt, Jing Yang:
Runtime Analysis for Self-adaptive Mutation Rates. 1012-1053 - Denis Antipov, Benjamin Doerr:
A Tight Runtime Analysis for the (μ + λ ) EA. 1054-1095 - Johannes Lengler, Dirk Sudholt, Carsten Witt:
The Complex Parameter Landscape of the Compact Genetic Algorithm. 1096-1137 - Andrew M. Sutton:
Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String Problem. 1138-1163
Volume 83, Number 5, May 2021
- Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés:
The Inverse Voronoi Problem in Graphs II: Trees. 1165-1200 - Benjamin Bergougnoux, Eduard Eiben, Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan:
Towards a Polynomial Kernel for Directed Feedback Vertex Set. 1201-1221 - Stefano Leonardi, Gianpiero Monaco, Piotr Sankowski, Qiang Zhang:
Budget Feasible Mechanisms on Matroids. 1222-1237 - Chi-Yeh Chen, Sun-Yuan Hsieh, Hoàng-Oanh Le, Van Bang Le, Sheng-Lung Peng:
Matching Cut in Graphs with Large Minimum Degree. 1238-1255 - Marios Mavronicolas, Loizos Michael, Vicky Papadopoulou Lesta, Giuseppe Persiano, Anna Philippou, Paul G. Spirakis:
The Price of Defense. 1256-1315 - Hugo A. Akitaya, Esther M. Arkin, Mirela Damian, Erik D. Demaine, Vida Dujmovic, Robin Y. Flatland, Matias Korman, Belén Palop, Irene Parada, André van Renssen, Vera Sacristán:
Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers. 1316-1351 - Yann Disser, Andreas Emil Feldmann, Max Klimm, Jochen Könemann:
Travelling on Graphs with Small Highway Dimension. 1352-1370 - Marc Bury, Michele Gentili, Chris Schwiegelshohn, Mara Sorella:
Polynomial Time Approximation Schemes for All 1-Center Problems on Metric Rational Set Similarities. 1371-1392 - Stéphane Bessy, Marin Bougeret, R. Krithika, Abhishek Sahu, Saket Saurabh, Jocelyn Thiebaut, Meirav Zehavi:
Packing Arc-Disjoint Cycles in Tournaments. 1393-1420 - Gabriel L. Duarte, Hiroshi Eto, Tesshu Hanaka, Yasuaki Kobayashi, Yusuke Kobayashi, Daniel Lokshtanov, Lehilton L. C. Pedrosa, Rafael C. S. Schouery, Uéverton S. Souza:
Computing the Largest Bond and the Maximum Connected Cut of a Graph. 1421-1458 - Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes:
Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between. 1459-1492 - Ágnes Cseh, Telikepalli Kavitha:
Popular Matchings in Complete Graphs. 1493-1523 - Erik D. Demaine, Yamming Huang, Chung-Shou Liao, Kunihiko Sadakane:
Approximating the Canadian Traveller Problem with Online Randomization. 1524-1543 - Pat Morin:
A Fast Algorithm for the Product Structure of Planar Graphs. 1544-1558 - Britta Dorn, Ronald de Haan, Ildikó Schlotter:
Obtaining a Proportional Allocation by Deleting Items. 1559-1603
Volume 83, Number 6, June 2021
- Robert Ganian, Sebastian Ordyniak, M. S. Ramanujan:
On Structural Parameterizations of the Edge Disjoint Paths Problem. 1605-1637 - Jie Zhang:
Average-Case Approximation Ratio of Scheduling without Payments. 1638-1652 - Yasushi Kawase, Kei Kimura, Kazuhisa Makino, Hanna Sumita:
Optimal Matroid Partitioning Problems. 1653-1676 - Guilherme de C. M. Gomes, Ignasi Sau:
Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization. 1677-1706 - Djamal Belazzougui, Travis Gagie, J. Ian Munro, Gonzalo Navarro, Yakov Nekrich:
Range Majorities and Minorities in Arrays. 1707-1733 - Alexander Grigoriev, Tim A. Hartmann, Stefan Lendl, Gerhard J. Woeginger:
Dispersing Obnoxious Facilities on a Graph. 1734-1749 - Susanne Albers, Arindam Khan, Leon Ladewig:
Improved Online Algorithms for Knapsack and GAP in the Random Order Model. 1750-1785 - Jesper Jansson, Konstantinos Mampentzidis, Ramesh Rajaby, Wing-Kin Sung:
Computing the Rooted Triplet Distance Between Phylogenetic Networks. 1786-1828 - Marc Roth:
Parameterized Counting of Partially Injective Homomorphisms. 1829-1860 - Jayakrishnan Madathil, Roohani Sharma, Meirav Zehavi:
A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs. 1861-1884 - Sariel Har-Peled, Mitchell Jones, Saladi Rahul:
Active-Learning a Convex Body in Low Dimensions. 1885-1917 - José A. Soto, Claudio Telha:
Independent Sets and Hitting Sets of Bicolored Rectangular Families. 1918-1952
Volume 83, Number 7, July 2021
- Shu Zhang, Daming Zhu, Haitao Jiang, Jiong Guo, Haodi Feng, Xiaowen Liu:
Sorting a Permutation by Best Short Swaps. 1953-1979 - Kook Jin Ahn, Graham Cormode, Sudipto Guha, Andrew McGregor, Anthony Wirth:
Correlation Clustering in Data Streams. 1980-2017 - Athanasios L. Konstantinidis, Charis Papadopoulos:
Cluster Deletion on Interval Graphs and Split Related Graphs. 2018-2046 - János Balogh, József Békési, György Dósa, Leah Epstein, Asaf Levin:
A New Lower Bound for Classic Online Bin Packing. 2047-2062 - Tom Davot, Annie Chateau, Rodolphe Giroudeau, Mathias Weller, Dorine Tabary:
Producing Genomic Sequences after Genome Scaffolding with Ambiguous Paths: Complexity, Approximation and Lower Bounds. 2063-2095 - Eun Jung Kim, O-joung Kwon:
A Polynomial Kernel for Distance-Hereditary Vertex Deletion. 2096-2141 - Panagiotis Charalampopoulos, Tomasz Kociumaka, Manal Mohamed, Jakub Radoszewski, Wojciech Rytter, Tomasz Walen:
Internal Dictionary Matching. 2142-2169 - Fedor V. Fomin, Petr A. Golovach:
Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs. 2170-2214 - Laurent Feuilloley, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, Éric Rémila, Ioan Todinca:
Compact Distributed Certification of Planar Graphs. 2215-2244 - Gill Barequet, Minati De, Michael T. Goodrich:
Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex Polygons. 2245-2272 - Ahmad Biniaz, Sergio Cabello, Paz Carmi, Jean-Lou De Carufel, Anil Maheshwari, Saeed Mehrabi, Michiel Smid:
On the Minimum Consistent Subset Problem. 2273-2302 - Arindam Biswas, Venkatesh Raman, Saket Saurabh:
Approximation in (Poly-) Logarithmic Space. 2303-2331
Volume 83, Number 8, August 2021
- Florian Hörsch, Zoltán Szigeti:
The (2, k)-Connectivity Augmentation Problem: Algorithmic Aspects. 2333-2350 - Rémy Belmonte, Ignasi Sau:
On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings. 2351-2373 - Evripidis Bampis, Bruno Escoffier, Kevin Schewior, Alexandre Teiller:
Online Multistage Subset Maximization Problems. 2374-2399 - Douglas Soares Gonçalves, Carlile Lavor, Leo Liberti, Michael Souza:
A New Algorithm for the KDMDGP Subclass of Distance Geometry Problems with Exact Distances. 2400-2426 - Karthekeyan Chandrasekaran, Elena Grigorescu, Gabriel Istrate, Shubhang Kulkarni, Young-San Lin, Minshen Zhu:
The Maximum Binary Tree Problem. 2427-2468 - Bart M. P. Jansen, Jan Arne Telle:
Special Issue Dedicated to the 14th International Symposium on Parameterized and Exact Computation. 2469-2470 - Giordano Da Lozzo, David Eppstein, Michael T. Goodrich, Siddharth Gupta:
C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width. 2471-2502 - Yoichi Iwata, Yusuke Kobayashi:
Improved Analysis of Highest-Degree Branching for Feedback Vertex Set. 2503-2520 - Gregory Rosenthal:
Beating Treewidth for Average-Case Subgraph Isomorphism. 2521-2551 - Benjamin Aram Berendsohn, László Kozma, Dániel Marx:
Finding and Counting Permutations via CSPs. 2552-2577 - Marco Bressan:
Faster algorithms for counting subgraphs in sparse graphs. 2578-2605 - Édouard Bonnet, Nidhi Purohit:
Metric Dimension Parameterized By Treewidth. 2606-2633 - Jana Novotná, Karolina Okrasa, Michal Pilipczuk, Pawel Rzazewski, Erik Jan van Leeuwen, Bartosz Walczak:
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs. 2634-2650
Volume 83, Number 9, September 2021
- Florent Foucaud, Benjamin Gras, Anthony Perez, Florian Sikora:
On the Complexity of Broadcast Domination and Multipacking in Digraphs. 2651-2677 - Koki Hamada, Shuichi Miyazaki, Kazuya Okamoto:
Strongly Stable and Maximum Weakly Stable Noncrossing Matchings. 2678-2696 - Toru Hasunuma:
Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions. 2697-2718 - Li-Hsuan Chen, Ling-Ju Hung, Henri Lotze, Peter Rossmanith:
Online Node- and Edge-Deletion Problems with Advice. 2719-2753 - Arnaud Casteigts, Anne-Sophie Himmel, Hendrik Molter, Philipp Zschoche:
Finding Temporal Paths Under Waiting Time Constraints. 2754-2802 - Susanne Albers, Maximilian Janke:
Scheduling in the Random-Order Model. 2803-2832 - Susanne Albers, Arindam Khan, Leon Ladewig:
Best Fit Bin Packing with Random Order Revisited. 2833-2858 - Iqra Altaf Gillani, Amitabha Bagchi:
A Queueing Network-Based Distributed Laplacian Solver. 2859-2894 - Yiannis Giannakopoulos, Alexander Hammerl, Diogo Poças:
A New Lower Bound for Deterministic Truthful Scheduling. 2895-2913 - Valentin Bartier, Nicolas Bousquet, Clément Dallard, Kyle Lomer, Amer E. Mouawad:
On Girth and the Parameterized Complexity of Token Sliding and Token Jumping. 2914-2951 - Leah Epstein, Elena Kleiman:
Selfish Vector Packing. 2952-2988 - Dror Rawitz, Adi Rosén:
Online Budgeted Maximum Coverage. 2989-3014
Volume 83, Number 10, October 2021
- Editor's Note: Special Issue on Genetic and Evolutionary Computation. 3015-3016
- Benjamin Doerr, Timo Kötzing:
Multiplicative Up-Drift. 3017-3058 - Benjamin Doerr:
The Runtime of the Compact Genetic Algorithm on Jump Functions. 3059-3107 - Benjamin Doerr, Carola Doerr, Johannes Lengler:
Self-Adjusting Mutation Rates with Provably Optimal Success Rules. 3108-3147 - Jakob Bossek, Frank Neumann, Pan Peng, Dirk Sudholt:
Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem. 3148-3179 - Andrew M. Sutton, Carsten Witt:
Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs. 3180-3208 - Frank Neumann, Mojgan Pourhassan, Carsten Witt:
Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint. 3209-3237 - Per Kristian Lehre, Phan Trung Hai Nguyen:
Runtime Analyses of the Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes. 3238-3280
Volume 83, Number 11, November 2021
- Steven Chaplick, Martin Töpfer, Jan Voborník, Peter Zeman:
On H-Topological Intersection Graphs. 3281-3318 - Michael Elkin, Ofer Neiman:
Near Isometric Terminal Embeddings for Doubling Metrics. 3319-3337 - Mathew C. Francis, Rian Neogi, Venkatesh Raman:
Recognizing k-Clique Extendible Orderings. 3338-3362 - Arnold T. Saunders:
A Class of Random Recursive Tree Algorithms with Deletion. 3363-3378 - Seungbum Jo, Rahul Lingala, Srinivasa Rao Satti:
Encoding Two-Dimensional Range Top-k Queries. 3379-3402 - Eleni C. Akrida, Argyrios Deligkas, Themistoklis Melissourgos, Paul G. Spirakis:
Connected Subgraph Defense Games. 3403-3431 - José Fuentes-Sepúlveda, Diego Seco, Raquel Viaña:
Succinct Encoding of Binary Strings Representing Triangulations. 3432-3468 - Magnús M. Halldórsson, Guy Kortsarz, Pradipta Mitra, Tigran Tonoyan:
Network Design under General Wireless Interference. 3469-3490 - Jongmin Choi, Sergio Cabello, Hee-Kap Ahn:
Maximizing Dominance in the Plane and its Applications. 3491-3513