Volume 82, Number 12, December 2020
Dynamic and Internal Longest Common Substring.

Amihood Amir Panagiotis Charalampopoulos Solon P. Pissis Jakub Radoszewski

On the Benefits of Populations for the Exploitation Speed of Standard Steady-State Genetic Algorithms.

Dogan Corus Pietro S. Oliveto

An Adversarial Model for Scheduling with Testing.

Christoph Dürr Thomas Erlebach Nicole Megow Julie Meißner

On Scheduling Coflows.

Saba Ahmadi Samir Khuller Manish Purohit Sheng Yang

Enumerating k-Arc-Connected Orientations.

Sarah Blind Kolja Knauer Petru Valicov

Subgraph Isomorphism on Graph Classes that Exclude a Substructure.

Hans L. Bodlaender Tesshu Hanaka Yasuaki Kobayashi Yusuke Kobayashi Yoshio Okamoto Yota Otachi Tom C. van der Zanden

The Power of Linear-Time Data Reduction for Maximum Matching.

George B. Mertzios André Nichterlein Rolf Niedermeier

Using a Min-Cut Generalisation to Go Beyond Boolean Surjective VCSPs.

Gregor Matl Stanislav Zivný

Fault Tolerant Approximate BFS Structures with Additive Stretch.

Merav Parter David Peleg

Non-preemptive Scheduling in a Smart Grid Model and Its Implications on Machine Minimization.

Fu-Hong Liu Hsiang-Hsuan Liu Prudence W. H. Wong


Volume 82, Number 11, November 2020
Correction to: Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks.

Zengfeng Huang Ke Yi Qin Zhang

Efficient Online String Matching Based on Characters Distance Text Sampling.

Simone Faro Francesco Pio Marino Arianna Pavone

Greed is Good for Deterministic Scale-Free Networks.

Ankit Chauhan Tobias Friedrich Ralf Rothenberger

Explicit Correlation Amplifiers for Finding Outlier Correlations in Deterministic Subquadratic Time.

Matti Karppa Petteri Kaski Jukka Kohonen Padraig Ó Catháin

Embedding Graphs into Embedded Graphs.

Radoslav Fulek

Deterministic Treasure Hunt in the Plane with Angular Hints.

Sébastien Bouchard Yoann Dieudonné Andrzej Pelc Franck Petit

Efficient 1-Space Bounded Hypercube Packing Algorithm.

Paulina Grzegorek Janusz Januszewski Lukasz Zielonka

Lempel-Ziv-Like Parsing in Small Space.

Dmitry Kosolobov Daniel Valenzuela Gonzalo Navarro Simon J. Puglisi

Dynamic Clustering to Minimize the Sum of Radii.

Monika Henzinger Dariusz Leniowski Claire Mathieu

Local Search Algorithms for the Maximum Carpool Matching Problem.

Gilad Kutiel Dror Rawitz

Improved Solution to Data Gathering with Mobile Mule.

Yoad Zur Michael Segal


Volume 82, Number 10, October 2020
Correction to: Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints.

Feng Shi Martin Schirneck Tobias Friedrich Timo Kötzing Frank Neumann

Approximating Global Optimum for Probabilistic Truth Discovery.

Shi Li Jinhui Xu Minwei Ye

Characterizing Star-PCGs.

Mingyu Xiao Hiroshi Nagamochi

Special Issue on Computing and Combinatorics.

Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs.

An Zhang Yong Chen Zhi-Zhong Chen Guohui Lin

The Inverse Voronoi Problem in Graphs I: Hardness.

Édouard Bonnet Sergio Cabello Bojan Mohar Hebert Pérez-Rosés

Upward Planar Morphs.

Giordano Da Lozzo Giuseppe Di Battista Fabrizio Frati Maurizio Patrignani Vincenzo Roselli

Computational Aspects of Ordered Integer Partitions with Bounds.

Roland Glück Dominik Köppl

Lipschitz Continuity and Approximate Equilibria.

Argyrios Deligkas John Fearnley Paul G. Spirakis

On the Approximate Compressibility of Connected Vertex Cover.

Diptapriyo Majumdar M. S. Ramanujan Saket Saurabh

Sequential Metric Dimension.

Julien Bensmail Dorian Mazauric Fionn Mc Inerney Nicolas Nisse Stéphane Pérennes

On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest.

Konrad K. Dabrowski Carl Feghali Matthew Johnson Giacomo Paesani Daniël Paulusma Pawel Rzazewski

Paired-Domination Problem on Distance-Hereditary Graphs.

Ching-Chi Lin Keng-Chu Ku Chan-Hung Hsu

Sensor Network Topology Design and Analysis for Efficient Data Gathering by a Mobile Mule.

Harel Yedidsion Stav Ashur Aritra Banik Paz Carmi Matthew J. Katz Michael Segal

Online Stochastic Matching: New Algorithms and Bounds.

Brian Brubach Karthik Abinav Sankararaman Aravind Srinivasan Pan Xu

A Unified Model and Algorithms for Temporal Map Labeling.

Andreas Gemsa Benjamin Niedermann Martin Nöllenburg


Volume 82, Number 9, September 2020
Compression of Dynamic Graphs Generated by a Duplication Model.

Krzysztof Turowski Abram Magner Wojciech Szpankowski

On the Approximability of the Stable Matching Problem with Ties of Size Two.

Robert Chiang Kanstantsin Pashkovich

Parameterized Multi-Scenario Single-Machine Scheduling Problems.

Danny Hermelin George Manoussakis Michael L. Pinedo Dvir Shabtay Liron Yedidsion

The Complexity of Tree Partitioning.

Zhao An Qilong Feng Iyad Kanj Ge Xia

Independent Set Reconfiguration Parameterized by Modular-Width.

Rémy Belmonte Tesshu Hanaka Michael Lampis Hirotaka Ono Yota Otachi

Queue Layouts of Planar 3-Trees.

Jawaherul Md. Alam Michael A. Bekos Martin Gronemann Michael Kaufmann Sergey Pupyrev

A $3+\varOmega (1)$ Lower Bound for Page Migration.

Akira Matsubayashi

An Efficient Exhaustive Search Algorithm for the Escherization Problem.

Yuichi Nagata Shinji Imahori

The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures.

Refael Hassin R. Ravi F. Sibel Salman Danny Segev

On the Tractability of Optimization Problems on H-Graphs.

Fedor V. Fomin Petr A. Golovach Jean-Florent Raymond

An Efficient Sum Query Algorithm for Distance-Based Locally Dominating Functions.

Ziyun Huang Jinhui Xu

A New Vertex Coloring Heuristic and Corresponding Chromatic Number.

Manouchehr Zaker


Volume 82, Number 8, August 2020
Parameterized Complexity of Independent Set in H-Free Graphs.

Édouard Bonnet Nicolas Bousquet Pierre Charbit Stéphan Thomassé Rémi Watrigant

Parameterized Leaf Power Recognition via Embedding into Graph Products.

David Eppstein Elham Havvaei

Dual Parameterization of Weighted Coloring.

Júlio Araújo Victor A. Campos Carlos Vinícius G. C. Lima Vinícius Fernandes dos Santos Ignasi Sau Ana Silva

Multivariate Analysis of Orthogonal Range Searching and Graph Distances.

Karl Bringmann Thore Husfeldt Måns Magnusson

Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness.

Marc Roth Johannes Schmitt

On the Distance Identifying Set Meta-problem and Applications to the Complexity of Identifying Problems on Graphs.

Florian Barbero Lucas Isenmann Jocelyn Thiebaut

Best-Case and Worst-Case Sparsifiability of Boolean CSPs.

Hubie Chen Bart M. P. Jansen Astrid Pieterse

The Parameterised Complexity of Computing the Maximum Modularity of a Graph.

Kitty Meeks Fiona Skerman

A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions.

Kustaa Kangas Mikko Koivisto Sami Salonen

Multi-budgeted Directed Cuts.

Stefan Kratsch Shaohua Li Dániel Marx Marcin Pilipczuk Magnus Wahlström

Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation.

Christophe Paul Michal Pilipczuk


Volume 82, Number 7, July 2020
On the Optimality of Tape Merge of Two Lists with Similar Size.

Qian Li Xiaoming Sun Jialin Zhang

The Distance-Constrained Matroid Median Problem.

Naoyuki Kamiyama

Compressed Dynamic Range Majority and Minority Data Structures.

Travis Gagie Meng He Gonzalo Navarro

The Generalized Definitions of the Two-Dimensional Largest Common Substructure Problems.

Huang-Ting Chan Hsuan-Tsung Chiu Chang-Biau Yang Yung-Hsing Peng

Parameterized Aspects of Strong Subgraph Closure.

Petr A. Golovach Pinar Heggernes Athanasios L. Konstantinidis Paloma T. Lima Charis Papadopoulos

The Parameterized Hardness of the k-Center Problem in Transportation Networks.

Andreas Emil Feldmann Dániel Marx

Robust Reoptimization of Steiner Trees.

Keshav Goyal Tobias Mömke

Parameterized Complexity of Conflict-Free Matchings and Paths.

Akanksha Agrawal Pallavi Jain Lawqueen Kanesh Saket Saurabh

Parameterized Orientable Deletion.

Tesshu Hanaka Ioannis Katsikarelis Michael Lampis Yota Otachi Florian Sikora

Placing Labels in Road Maps: Algorithms and Complexity.

Andreas Gemsa Benjamin Niedermann Martin Nöllenburg

Subgraph Complementation.

Fedor V. Fomin Petr A. Golovach Torstein J. F. Strømme Dimitrios M. Thilikos

Colouring (Pr + Ps)-Free Graphs.

Tereza Klimosová Josef Malík Tomás Masarík Jana Novotná Daniël Paulusma Veronika Slívová

Shortest Paths in the Plane with Obstacle Violations.

John Hershberger Neeraj Kumar Subhash Suri

Walking Through Waypoints.

Saeed Akhoondian Amiri Klaus-Tycho Foerster Stefan Schmid

Why Did the Shape of Your Network Change? (On Detecting Network Anomalies via Non-local Curvatures).

Bhaskar DasGupta Mano Vikash Janardhanan Farzane Yahyanejad


Volume 82, Number 6, June 2020
Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs.

Michal Pilipczuk Erik Jan van Leeuwen Andreas Wiese

High-Dimensional Approximate r-Nets.

Zeta Avarikioti Ioannis Z. Emiris Loukas Kavouras Ioannis Psarros

An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width.

Benjamin Bergougnoux Mamadou Moustapha Kanté O-joung Kwon

Nested Convex Bodies are Chaseable.

Nikhil Bansal Martin Böhm Marek Eliás Grigorios Koumoutsos Seeun William Umboh

On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths.

Júlio Araújo Victor A. Campos Ana Karolinna Maia Ignasi Sau Ana Silva

Speeding Up the Gomory-Hu Parallel Cut Tree Algorithm with Efficient Graph Contractions.

Charles Maske Jaime Cohen Elias P. Duarte Jr.

On the Complexity of Computing Treebreadth.

Guillaume Ducoffe Sylvain Legay Nicolas Nisse

Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs.

Alessio Conte Roberto Grossi Andrea Marino Luca Versari


Volume 82, Number 5, May 2020
Energy-Optimal Routes for Battery Electric Vehicles.

Moritz Baum Julian Dibbelt Thomas Pajor Jonas Sauer Dorothea Wagner Tobias Zündorf

Solving and Sampling with Many Solutions.

Jean Cardinal Jerri Nummenpalo Emo Welzl

The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon.

Eunjin Oh Luis Barba Hee-Kap Ahn

Stable Matching with Uncertain Linear Preferences.

Haris Aziz Péter Biró Serge Gaspers Ronald de Haan Nicholas Mattei Baharak Rastegari

Consensus Strings with Small Maximum Distance and Small Distance Sum.

Laurent Bulteau Markus L. Schmid

Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts.

Takuya Takagi Shunsuke Inenaga Hiroki Arimura Dany Breslauer Diptarama Hendrian

An Analysis of Budgeted Parallel Search on Conditional Galton-Watson Trees.

David Avis Luc Devroye

Dividing Splittable Goods Evenly and With Limited Fragmentation.

Peter Damaschke

Testing Proximity to Subspaces: Approximate ℓ ∞ Minimization in Constant Time.

Kohei Hayashi Yuichi Yoshida

Reachability Oracles for Directed Transmission Graphs.

Haim Kaplan Wolfgang Mulzer Liam Roditty Paul Seiferth

A Constant-Time Algorithm for Middle Levels Gray Codes.

Torsten Mütze Jerri Nummenpalo

Computing a Pessimistic Stackelberg Equilibrium with Multiple Followers: The Mixed-Pure Case.

Stefano Coniglio Nicola Gatti Alberto Marchesi

Stable Matchings with Covering Constraints: A Complete Computational Trichotomy.

Matthias Mnich Ildikó Schlotter

Stochastic Dominance and the Bijective Ratio of Online Algorithms.

Spyros Angelopoulos Marc P. Renault Pascal Schweitzer

Non-Monochromatic and Conflict-Free Colorings on Tree Spaces and Planar Network Spaces.

Boris Aronov Mark de Berg Aleksandar Markovic Gerhard J. Woeginger