0178-4617

ALMCA - 2021 - volume 83 论文列表
点击这里查看 Algorithmica 的JCR分区、影响因子等信息
Volume 83, Number 11, November 2021
Correction to: Outer 1-Planar Graphs.

Christopher Auer Christian Bachmaier Franz J. Brandenburg Andreas Gleißner Kathrin Hanauer Daniel Neuwirth Josef Reislhuber

Translation Invariant Fréchet Distance Queries.

Joachim Gudmundsson André van Renssen Zeinab Saeidi Sampson Wong

Maximizing Dominance in the Plane and its Applications.

Jongmin Choi Sergio Cabello Hee-Kap Ahn

Network Design under General Wireless Interference.

Magnús M. Halldórsson Guy Kortsarz Pradipta Mitra Tigran Tonoyan

Succinct Encoding of Binary Strings Representing Triangulations.

José Fuentes-Sepúlveda Diego Seco Raquel Viaña

Connected Subgraph Defense Games.

Eleni C. Akrida Argyrios Deligkas Themistoklis Melissourgos Paul G. Spirakis

Encoding Two-Dimensional Range Top-k Queries.

Seungbum Jo Rahul Lingala Srinivasa Rao Satti

A Class of Random Recursive Tree Algorithms with Deletion.

Arnold T. Saunders

Recognizing k-Clique Extendible Orderings.

Mathew C. Francis Rian Neogi Venkatesh Raman

Near Isometric Terminal Embeddings for Doubling Metrics.

Michael Elkin Ofer Neiman

On H-Topological Intersection Graphs.

Steven Chaplick Martin Töpfer Jan Voborník Peter Zeman

Volume 83, Number 10, October 2021
Runtime Analyses of the Population-Based Univariate Estimation of Distribution Algorithms on LeadingOnes.

Per Kristian Lehre Phan Trung Hai Nguyen

Improved Runtime Results for Simple Randomised Search Heuristics on Linear Functions with a Uniform Constraint.

Frank Neumann Mojgan Pourhassan Carsten Witt

Lower Bounds on the Runtime of Crossover-Based Algorithms via Decoupling and Family Graphs.

Andrew M. Sutton Carsten Witt

Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem.

Jakob Bossek Frank Neumann Pan Peng Dirk Sudholt

Self-Adjusting Mutation Rates with Provably Optimal Success Rules.

Benjamin Doerr Carola Doerr Johannes Lengler

The Runtime of the Compact Genetic Algorithm on Jump Functions.

Benjamin Doerr

Multiplicative Up-Drift.

Benjamin Doerr Timo Kötzing

Editor's Note: Special Issue on Genetic and Evolutionary Computation.

Volume 83, Number 9, September 2021
Online Budgeted Maximum Coverage.

Dror Rawitz Adi Rosén

Selfish Vector Packing.

Leah Epstein Elena Kleiman

On Girth and the Parameterized Complexity of Token Sliding and Token Jumping.

Valentin Bartier Nicolas Bousquet Clément Dallard Kyle Lomer Amer E. Mouawad

A New Lower Bound for Deterministic Truthful Scheduling.

Yiannis Giannakopoulos Alexander Hammerl Diogo Poças

A Queueing Network-Based Distributed Laplacian Solver.

Iqra Altaf Gillani Amitabha Bagchi

Best Fit Bin Packing with Random Order Revisited.

Susanne Albers Arindam Khan Leon Ladewig

Scheduling in the Random-Order Model.

Susanne Albers Maximilian Janke

Finding Temporal Paths Under Waiting Time Constraints.

Arnaud Casteigts Anne-Sophie Himmel Hendrik Molter Philipp Zschoche

Online Node- and Edge-Deletion Problems with Advice.

Li-Hsuan Chen Ling-Ju Hung Henri Lotze Peter Rossmanith

Connectivity Keeping Trees in 2-Connected Graphs with Girth Conditions.

Toru Hasunuma

Strongly Stable and Maximum Weakly Stable Noncrossing Matchings.

Koki Hamada Shuichi Miyazaki Kazuya Okamoto

On the Complexity of Broadcast Domination and Multipacking in Digraphs.

Florent Foucaud Benjamin Gras Anthony Perez Florian Sikora

Volume 83, Number 8, August 2021
Subexponential-Time Algorithms for Finding Large Induced Sparse Subgraphs.

Jana Novotná Karolina Okrasa Michal Pilipczuk Pawel Rzazewski Erik Jan van Leeuwen Bartosz Walczak

Metric Dimension Parameterized By Treewidth.

Édouard Bonnet Nidhi Purohit

Faster algorithms for counting subgraphs in sparse graphs.

Marco Bressan

Finding and Counting Permutations via CSPs.

Benjamin Aram Berendsohn László Kozma Dániel Marx

Beating Treewidth for Average-Case Subgraph Isomorphism.

Gregory Rosenthal

Improved Analysis of Highest-Degree Branching for Feedback Vertex Set.

Yoichi Iwata Yusuke Kobayashi

C-Planarity Testing of Embedded Clustered Graphs with Bounded Dual Carving-Width.

Giordano Da Lozzo David Eppstein Michael T. Goodrich Siddharth Gupta

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

Bart M. P. Jansen Jan Arne Telle

The Maximum Binary Tree Problem.

Karthekeyan Chandrasekaran Elena Grigorescu Gabriel Istrate Shubhang Kulkarni Young-San Lin Minshen Zhu

A New Algorithm for the KDMDGP Subclass of Distance Geometry Problems with Exact Distances.

Douglas Soares Gonçalves Carlile Lavor Leo Liberti Michael Souza

Online Multistage Subset Maximization Problems.

Evripidis Bampis Bruno Escoffier Kevin Schewior Alexandre Teiller

On the Complexity of Finding Large Odd Induced Subgraphs and Odd Colorings.

Rémy Belmonte Ignasi Sau

The (2, k)-Connectivity Augmentation Problem: Algorithmic Aspects.

Florian Hörsch Zoltán Szigeti

Volume 83, Number 7, July 2021
Approximation in (Poly-) Logarithmic Space.

Arindam Biswas Venkatesh Raman Saket Saurabh

On the Minimum Consistent Subset Problem.

Ahmad Biniaz Sergio Cabello Paz Carmi Jean-Lou De Carufel Anil Maheshwari Saeed Mehrabi Michiel Smid

Convex-Straight-Skeleton Voronoi Diagrams for Segments and Convex Polygons.

Gill Barequet Minati De Michael T. Goodrich

Compact Distributed Certification of Planar Graphs.

Laurent Feuilloley Pierre Fraigniaud Pedro Montealegre Ivan Rapaport Éric Rémila Ioan Todinca

Subexponential Parameterized Algorithms and Kernelization on Almost Chordal Graphs.

Fedor V. Fomin Petr A. Golovach

Internal Dictionary Matching.

Panagiotis Charalampopoulos Tomasz Kociumaka Manal Mohamed Jakub Radoszewski Wojciech Rytter Tomasz Walen

A Polynomial Kernel for Distance-Hereditary Vertex Deletion.

Eun Jung Kim O-joung Kwon

Producing Genomic Sequences after Genome Scaffolding with Ambiguous Paths: Complexity, Approximation and Lower Bounds.

Tom Davot Annie Chateau Rodolphe Giroudeau Mathias Weller Dorine Tabary

A New Lower Bound for Classic Online Bin Packing.

János Balogh József Békési György Dósa Leah Epstein Asaf Levin

Cluster Deletion on Interval Graphs and Split Related Graphs.

Athanasios L. Konstantinidis Charis Papadopoulos

Correlation Clustering in Data Streams.

Kook Jin Ahn Graham Cormode Sudipto Guha Andrew McGregor Anthony Wirth

Sorting a Permutation by Best Short Swaps.

Shu Zhang Daming Zhu Haitao Jiang Jiong Guo Haodi Feng Xiaowen Liu

Volume 83, Number 6, June 2021
Independent Sets and Hitting Sets of Bicolored Rectangular Families.

José A. Soto Claudio Telha

Active-Learning a Convex Body in Low Dimensions.

Sariel Har-Peled Mitchell Jones Saladi Rahul

A Sub-exponential FPT Algorithm and a Polynomial Kernel for Minimum Directed Bisection on Semicomplete Digraphs.

Jayakrishnan Madathil Roohani Sharma Meirav Zehavi

Parameterized Counting of Partially Injective Homomorphisms.

Marc Roth

Computing the Rooted Triplet Distance Between Phylogenetic Networks.

Jesper Jansson Konstantinos Mampentzidis Ramesh Rajaby Wing-Kin Sung

Improved Online Algorithms for Knapsack and GAP in the Random Order Model.

Susanne Albers Arindam Khan Leon Ladewig

Dispersing Obnoxious Facilities on a Graph.

Alexander Grigoriev Tim A. Hartmann Stefan Lendl Gerhard J. Woeginger

Range Majorities and Minorities in Arrays.

Djamal Belazzougui Travis Gagie J. Ian Munro Gonzalo Navarro Yakov Nekrich

Finding Cuts of Bounded Degree: Complexity, FPT and Exact Algorithms, and Kernelization.

Guilherme de C. M. Gomes Ignasi Sau

Optimal Matroid Partitioning Problems.

Yasushi Kawase Kei Kimura Kazuhisa Makino Hanna Sumita

Average-Case Approximation Ratio of Scheduling without Payments.

Jie Zhang

On Structural Parameterizations of the Edge Disjoint Paths Problem.

Robert Ganian Sebastian Ordyniak M. S. Ramanujan

Volume 83, Number 5, May 2021
Obtaining a Proportional Allocation by Deleting Items.

Britta Dorn Ronald de Haan Ildikó Schlotter

A Fast Algorithm for the Product Structure of Planar Graphs.

Pat Morin

Approximating the Canadian Traveller Problem with Online Randomization.

Erik D. Demaine Yamming Huang Chung-Shou Liao Kunihiko Sadakane

Popular Matchings in Complete Graphs.

Ágnes Cseh Telikepalli Kavitha

Eternal Domination: D-Dimensional Cartesian and Strong Grids and Everything in Between.

Fionn Mc Inerney Nicolas Nisse Stéphane Pérennes

Computing the Largest Bond and the Maximum Connected Cut of a Graph.

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

Packing Arc-Disjoint Cycles in Tournaments.

Stéphane Bessy Marin Bougeret R. Krithika Abhishek Sahu Saket Saurabh Jocelyn Thiebaut Meirav Zehavi

Polynomial Time Approximation Schemes for All 1-Center Problems on Metric Rational Set Similarities.

Marc Bury Michele Gentili Chris Schwiegelshohn Mara Sorella

Travelling on Graphs with Small Highway Dimension.

Yann Disser Andreas Emil Feldmann Max Klimm Jochen Könemann

Universal Reconfiguration of Facet-Connected Modular Robots by Pivots: The O(1) Musketeers.

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

The Price of Defense.

Marios Mavronicolas Loizos Michael Vicky Papadopoulou Lesta Giuseppe Persiano Anna Philippou Paul G. Spirakis

Matching Cut in Graphs with Large Minimum Degree.

Chi-Yeh Chen Sun-Yuan Hsieh Hoàng-Oanh Le Van Bang Le Sheng-Lung Peng

Budget Feasible Mechanisms on Matroids.

Stefano Leonardi Gianpiero Monaco Piotr Sankowski Qiang Zhang

Towards a Polynomial Kernel for Directed Feedback Vertex Set.

Benjamin Bergougnoux Eduard Eiben Robert Ganian Sebastian Ordyniak M. S. Ramanujan

The Inverse Voronoi Problem in Graphs II: Trees.

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

Volume 83, Number 4, April 2021
Fixed-Parameter Tractability of Crossover: Steady-State GAs on the Closest String Problem.

Andrew M. Sutton

The Complex Parameter Landscape of the Compact Genetic Algorithm.

Johannes Lengler Dirk Sudholt Carsten Witt

A Tight Runtime Analysis for the (μ + λ ) EA.

Denis Antipov Benjamin Doerr

Runtime Analysis for Self-adaptive Mutation Rates.

Benjamin Doerr Carsten Witt Jing Yang

Analysing the Robustness of Evolutionary Algorithms to Noise: Refined Runtime Bounds and an Example Where Noise is Beneficial.

Dirk Sudholt

Analysis of Noisy Evolutionary Optimization When Sampling Fails.

Chao Qian Chao Bian Yang Yu Ke Tang Xin Yao

Runtime Performances of Randomized Search Heuristics for the Dynamic Weighted Vertex Cover Problem.

Feng Shi Frank Neumann Jianxin Wang

Preface to the Special Issue on Theory of Genetic and Evolutionary Computation.

Anne Auger Per Kristian Lehre

Volume 83, Number 2, February 2021
Simultaneous Feedback Edge Set: A Parameterized Perspective.

Akanksha Agrawal Fahad Panolan Saket Saurabh Meirav Zehavi

The Power of Cut-Based Parameters for Computing Edge-Disjoint Paths.

Robert Ganian Sebastian Ordyniak

Approximation Guarantee of OSP Mechanisms: The Case of Machine Scheduling and Facility Location.

Diodato Ferraioli Carmine Ventre

High Entropy Random Selection Protocols.

Harry Buhrman Matthias Christandl Michal Koucký Zvi Lotker Boaz Patt-Shamir Nikolai K. Vereshchagin

On Orthogonally Guarding Orthogonal Polygons with Bounded Treewidth.

Therese C. Biedl Saeed Mehrabi

Non-Greedy Online Steiner Trees on Outerplanar Graphs.

Akira Matsubayashi

On the Complexity of Colouring Antiprismatic Graphs.

Myriam Preissmann Cléophée Robin Nicolas Trotignon

Constrained Minimum Passage Time in Random Geometric Graphs.

Ghurumuruhan Ganesan

On the Tree Augmentation Problem.

Zeev Nutov

Covert Computation in Self-Assembled Circuits.

Angel A. Cantu Austin Luchsinger Robert T. Schweller Tim Wylie

The Complexity of Computational Problems About Nash Equilibria in Symmetric Win-Lose Games.

Vittorio Bilò Marios Mavronicolas

Fault-Tolerant Covering Problems in Metric Spaces.

Santanu Bhowmick Tanmay Inamdar Kasturi R. Varadarajan

Volume 83, Number 1, January 2021
CADbots: Algorithmic Aspects of Manipulating Programmable Matter with Finite Automata.

Sándor P. Fekete Robert Gmyr Sabrina Hugo Phillip Keldenich Christian Scheffer Arne Schmidt

Polynomial Treedepth Bounds in Linear Colorings.

Jeremy Kun Michael P. O'Brien Marcin Pilipczuk Blair D. Sullivan

Tight Bounds for Online Coloring of Basic Graph Classes.

Susanne Albers Sebastian Schraink

On Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem.

Robert Ganian Fabian Klute Sebastian Ordyniak

Distance and Routing Labeling Schemes for Cube-Free Median Graphs.

Victor Chepoi Arnaud Labourel Sébastien Ratel

List 3-Coloring Graphs with No Induced P6+rP3.

Maria Chudnovsky Shenwei Huang Sophie Spirkl Mingxian Zhong

Learning Privately with Labeled and Unlabeled Examples.

Amos Beimel Kobbi Nissim Uri Stemmer

Building a Nest by an Automaton.

Jurek Czyzowicz Dariusz Dereniowski Andrzej Pelc

Flip Distances Between Graph Orientations.

Oswin Aichholzer Jean Cardinal Tony Huynh Kolja Knauer Torsten Mütze Raphael Steiner Birgit Vogtenhuber

Privately Outsourcing Exponentiation to a Single Server: Cryptanalysis and Optimal Constructions.

Céline Chevalier Fabien Laguillaumie Damien Vergnaud

Iterative Partial Rounding for Vertex Cover with Hard Capacities.

Mong-Jen Kao

Parameterized Dynamic Cluster Editing.

Junjie Luo Hendrik Molter André Nichterlein Rolf Niedermeier