default search action
Algorithmica, Volume 82
Volume 82, Number 1, January 2020
- Aritra Banik, Fahad Panolan, Venkatesh Raman, Vibha Sahlot, Saket Saurabh:
Parameterized Complexity of Geometric Covering Problems Having Conflicts. 1-19 - Matthew Johnson, Giacomo Paesani, Daniël Paulusma:
Connected Vertex Cover for (sP1+P5)-Free Graphs. 20-40 - Aritra Banik, Pratibha Choudhary, Daniel Lokshtanov, Venkatesh Raman, Saket Saurabh:
A Polynomial Sized Kernel for Tracking Paths Problem. 41-63 - Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu:
Attenuate Locally, Win Globally: Attenuation-Based Frameworks for Online Stochastic Matching with Timeouts. 64-87 - Siu-Wing Cheng, Kai Jin, Lie Yan:
Extensions of Self-Improving Sorters. 88-106 - Arnab Ganguly, Rahul Shah, Sharma V. Thankachan:
Succinct Non-overlapping Indexing. 107-117 - Lars Jaffke, O-joung Kwon, Jan Arne Telle:
Mim-Width II. The Feedback Vertex Set Problem. 118-145 - Johanna E. Preißer, Jens M. Schmidt:
Computing Vertex-Disjoint Paths in Large Graphs Using MAOs. 146-162
Volume 82, Number 2, February 2020
- Yoshio Okamoto:
Guest Editorial: Selected Papers from ISAAC 2017. 163-164 - Aaron T. Becker, Sándor P. Fekete, Phillip Keldenich, Dominik Krupke, Christian Rieck, Christian Scheffer, Arne Schmidt:
Tilt Assembly: Algorithms for Micro-factories That Build Objects with Uniform External Forces. 165-187 - Yu Yokoi:
Envy-Free Matchings with Lower Quotas. 188-211 - Nathann Cohen, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes:
Study of a Combinatorial Game in Graphs Through Linear Programming. 212-244 - Edvin Berglin, Gerth Stølting Brodal:
A Simple Greedy Algorithm for Dynamic Graph Orientation. 245-259 - Michel Habib, Lalla Mouatadid:
Maximum Induced Matching Algorithms via Vertex Ordering Characterizations. 260-278 - Davide Bilò, Feliciano Colella, Luciano Gualà, Stefano Leucci, Guido Proietti:
An Improved Algorithm for Computing All the Best Swap Edges of a Tree Spanner. 279-299 - Vincenzo Bonifaci:
On the Convergence Time of a Natural Dynamics for Linear Programming. 300-315 - J. Ian Munro, Gonzalo Navarro, Yakov Nekrich:
Fast Compressed Self-indexes with Deterministic Linear-Time Construction. 316-337 - Casper Benjamin Freksen, Kasper Green Larsen:
On Using Toeplitz and Circulant Matrices for Johnson-Lindenstrauss Transforms. 338-354 - Therese Biedl, Markus Chimani, Martin Derka, Petra Mutzel:
Crossing Number for Graphs with Bounded Pathwidth. 355-384
Volume 82, Number 3, March 2020
- James Allen Fill, Mark Daniel Ward:
Special Issue on Analysis of Algorithms. 385 - Andrei Asinowski, Axel Bacher, Cyril Banderier, Bernhard Gittenberger:
Analytic Combinatorics of Lattice Paths with Forbidden Patterns, the Vectorial Kernel Method, and Generating Functions for Pushdown Automata. 386-428 - Clemens Heuberger, Daniel Krenn:
Asymptotic Analysis of Regular Sequences. 429-508 - Stefan Edelkamp, Armin Weiß, Sebastian Wild:
QuickXsort: A Fast Sorting Scheme in Theory and Practice. 509-588 - Michael Albert, Cecilia Holmgren, Tony Johansson, Fiona Skerman:
Embedding Small Digraphs and Permutations in Binary Trees and Split Trees. 589-615 - Svante Janson:
Patterns in Random Permutations Avoiding Some Sets of Multiple Patterns. 616-641 - Dimbinaina Ralaivaosaona, Matas Sileikis, Stephan G. Wagner:
A Central Limit Theorem for Almost Local Additive Tree Functionals. 642-679
Volume 82, Number 4, April 2020
- Gerardo Berbeglia, Gwenaël Joret:
Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments. 681-720 - Stefan Dobrev, Evangelos Kranakis, Danny Krizanc, Manuel Lafond, Ján Manuch, Lata Narayanan, Jaroslav Opatrny, Ladislav Stacho:
Weak Coverage of a Rectangular Barrier. 721-746 - Reut Levi, Dana Ron, Ronitt Rubinfeld:
Local Algorithms for Sparse Spanning Graphs. 747-786 - Tatsuya Matsuoka, Shun Sato:
Making Bidirected Graphs Strongly Connected. 787-807 - Hu Ding, Jinhui Xu:
A Unified Framework for Clustering Constrained Data Without Locality Property. 808-852 - Niels Grüttemeier, Christian Komusiewicz:
On the Relation of Strong Triadic Closure and Cluster Deletion. 853-880 - Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi:
Quadratic Vertex Kernel for Rainbow Matching. 881-897 - Vicente Acuña, Roberto Grossi, Giuseppe Francesco Italiano, Leandro Lima, Romeo Rizzi, Gustavo Sacomoto, Marie-France Sagot, Blerina Sinaimeri:
On Bubble Generators in Directed Graphs. 898-914 - Chih-Hung Liu:
A Nearly Optimal Algorithm for the Geodesic Voronoi Diagram of Points in a Simple Polygon. 915-937 - Marek Chrobak, Christoph Dürr, Aleksander Fabijan, Bengt J. Nilsson:
Online Clique Clustering. 938-965 - Yijie Han:
Sorting Real Numbers in $O\big (n\sqrt{\log n}\big )$ Time and Linear Space. 966-978 - Yijie Han:
Correction to: Sorting Real Numbers in $O(n\sqrt{\log n})$ Time and Linear Space. 979 - Titouan Carette, Mathieu Laurière, Frédéric Magniez:
Extended Learning Graphs for Triangle Finding. 980-1005 - Chien-Chung Huang, Naonori Kakimura, Yuichi Yoshida:
Streaming Algorithms for Maximizing Monotone Submodular Functions Under a Knapsack Constraint. 1006-1032 - Torben Hagerup:
Space-Efficient DFS and Applications to Connectivity Problems: Simpler, Leaner, Faster. 1033-1056 - Sayan Bhattacharya, Deeparnab Chakrabarty, Monika Henzinger:
Deterministic Dynamic Matching in O(1) Update Time. 1057-1080
Volume 82, Number 5, May 2020
- Boris Aronov, Mark de Berg, Aleksandar Markovic, Gerhard J. Woeginger:
Non-Monochromatic and Conflict-Free Colorings on Tree Spaces and Planar Network Spaces. 1081-1100 - Spyros Angelopoulos, Marc P. Renault, Pascal Schweitzer:
Stochastic Dominance and the Bijective Ratio of Online Algorithms. 1101-1135 - Matthias Mnich, Ildikó Schlotter:
Stable Matchings with Covering Constraints: A Complete Computational Trichotomy. 1136-1188 - Stefano Coniglio, Nicola Gatti, Alberto Marchesi:
Computing a Pessimistic Stackelberg Equilibrium with Multiple Followers: The Mixed-Pure Case. 1189-1238 - Torsten Mütze, Jerri Nummenpalo:
A Constant-Time Algorithm for Middle Levels Gray Codes. 1239-1258 - Haim Kaplan, Wolfgang Mulzer, Liam Roditty, Paul Seiferth:
Reachability Oracles for Directed Transmission Graphs. 1259-1276 - Kohei Hayashi, Yuichi Yoshida:
Testing Proximity to Subspaces: Approximate ℓ ∞ Minimization in Constant Time. 1277-1297 - Peter Damaschke:
Dividing Splittable Goods Evenly and With Limited Fragmentation. 1298-1328 - David Avis, Luc Devroye:
An Analysis of Budgeted Parallel Search on Conditional Galton-Watson Trees. 1329-1345 - Takuya Takagi, Shunsuke Inenaga, Hiroki Arimura, Dany Breslauer, Diptarama Hendrian:
Fully-Online Suffix Tree and Directed Acyclic Word Graph Construction for Multiple Texts. 1346-1377 - Laurent Bulteau, Markus L. Schmid:
Consensus Strings with Small Maximum Distance and Small Distance Sum. 1378-1409 - Haris Aziz, Péter Biró, Serge Gaspers, Ronald de Haan, Nicholas Mattei, Baharak Rastegari:
Stable Matching with Uncertain Linear Preferences. 1410-1433 - Eunjin Oh, Luis Barba, Hee-Kap Ahn:
The Geodesic Farthest-Point Voronoi Diagram in a Simple Polygon. 1434-1473 - Jean Cardinal, Jerri Nummenpalo, Emo Welzl:
Solving and Sampling with Many Solutions. 1474-1489 - Moritz Baum, Julian Dibbelt, Thomas Pajor, Jonas Sauer, Dorothea Wagner, Tobias Zündorf:
Energy-Optimal Routes for Battery Electric Vehicles. 1490-1546
Volume 82, Number 6, June 2020
- Alessio Conte, Roberto Grossi, Andrea Marino, Luca Versari:
Sublinear-Space and Bounded-Delay Algorithms for Maximal Clique Enumeration in Graphs. 1547-1573 - Guillaume Ducoffe, Sylvain Legay, Nicolas Nisse:
On the Complexity of Computing Treebreadth. 1574-1600 - Charles Maske, Jaime Cohen, Elias P. Duarte Jr.:
Speeding Up the Gomory-Hu Parallel Cut Tree Algorithm with Efficient Graph Contractions. 1601-1615 - Júlio Araújo, Victor A. Campos, Ana Karolinna Maia, Ignasi Sau, Ana Silva:
On the Complexity of Finding Internally Vertex-Disjoint Long Directed Paths. 1616-1639 - Nikhil Bansal, Martin Böhm, Marek Eliás, Grigorios Koumoutsos, Seeun William Umboh:
Nested Convex Bodies are Chaseable. 1640-1653 - Benjamin Bergougnoux, Mamadou Moustapha Kanté, O-joung Kwon:
An Optimal XP Algorithm for Hamiltonian Cycle on Graphs of Bounded Clique-Width. 1654-1674 - Zeta Avarikioti, Ioannis Z. Emiris, Loukas Kavouras, Ioannis Psarros:
High-Dimensional Approximate r-Nets. 1675-1702 - Michal Pilipczuk, Erik Jan van Leeuwen, Andreas Wiese:
Quasi-Polynomial Time Approximation Schemes for Packing and Covering Problems in Planar Graphs. 1703-1739
Volume 82, Number 7, July 2020
- Bhaskar DasGupta, Mano Vikash Janardhanan, Farzane Yahyanejad:
Why Did the Shape of Your Network Change? (On Detecting Network Anomalies via Non-local Curvatures). 1741-1783 - Saeed Akhoondian Amiri, Klaus-Tycho Foerster, Stefan Schmid:
Walking Through Waypoints. 1784-1812 - John Hershberger, Neeraj Kumar, Subhash Suri:
Shortest Paths in the Plane with Obstacle Violations. 1813-1832 - Tereza Klimosová, Josef Malík, Tomás Masarík, Jana Novotná, Daniël Paulusma, Veronika Slívová:
Colouring (Pr + Ps)-Free Graphs. 1833-1858 - Fedor V. Fomin, Petr A. Golovach, Torstein J. F. Strømme, Dimitrios M. Thilikos:
Subgraph Complementation. 1859-1880 - Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg:
Placing Labels in Road Maps: Algorithms and Complexity. 1881-1908 - Tesshu Hanaka, Ioannis Katsikarelis, Michael Lampis, Yota Otachi, Florian Sikora:
Parameterized Orientable Deletion. 1909-1938 - Akanksha Agrawal, Pallavi Jain, Lawqueen Kanesh, Saket Saurabh:
Parameterized Complexity of Conflict-Free Matchings and Paths. 1939-1965 - Keshav Goyal, Tobias Mömke:
Robust Reoptimization of Steiner Trees. 1966-1988 - Andreas Emil Feldmann, Dániel Marx:
The Parameterized Hardness of the k-Center Problem in Transportation Networks. 1989-2005 - Petr A. Golovach, Pinar Heggernes, Athanasios L. Konstantinidis, Paloma T. Lima, Charis Papadopoulos:
Parameterized Aspects of Strong Subgraph Closure. 2006-2038 - Huang-Ting Chan, Hsuan-Tsung Chiu, Chang-Biau Yang, Yung-Hsing Peng:
The Generalized Definitions of the Two-Dimensional Largest Common Substructure Problems. 2039-2062 - Travis Gagie, Meng He, Gonzalo Navarro:
Compressed Dynamic Range Majority and Minority Data Structures. 2063-2086 - Naoyuki Kamiyama:
The Distance-Constrained Matroid Median Problem. 2087-2106 - Qian Li, Xiaoming Sun, Jialin Zhang:
On the Optimality of Tape Merge of Two Lists with Similar Size. 2107-2132
Volume 82, Number 8, August 2020
- Christophe Paul, Michal Pilipczuk:
Special Issue Dedicated to the 13th International Symposium on Parameterized and Exact Computation. 2133-2134 - Stefan Kratsch, Shaohua Li, Dániel Marx, Marcin Pilipczuk, Magnus Wahlström:
Multi-budgeted Directed Cuts. 2135-2155 - Kustaa Kangas, Mikko Koivisto, Sami Salonen:
A Faster Tree-Decomposition Based Algorithm for Counting Linear Extensions. 2156-2173 - Kitty Meeks, Fiona Skerman:
The Parameterised Complexity of Computing the Maximum Modularity of a Graph. 2174-2199 - Hubie Chen, Bart M. P. Jansen, Astrid Pieterse:
Best-Case and Worst-Case Sparsifiability of Boolean CSPs. 2200-2242 - Florian Barbero, Lucas Isenmann, Jocelyn Thiebaut:
On the Distance Identifying Set Meta-problem and Applications to the Complexity of Identifying Problems on Graphs. 2243-2266 - Marc Roth, Johannes Schmitt:
Counting Induced Subgraphs: A Topological Approach to #W[1]-hardness. 2267-2291 - Karl Bringmann, Thore Husfeldt, Måns Magnusson:
Multivariate Analysis of Orthogonal Range Searching and Graph Distances. 2292-2315 - Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, Ana Silva:
Dual Parameterization of Weighted Coloring. 2316-2336 - David Eppstein, Elham Havvaei:
Parameterized Leaf Power Recognition via Embedding into Graph Products. 2337-2359 - Édouard Bonnet, Nicolas Bousquet, Pierre Charbit, Stéphan Thomassé, Rémi Watrigant:
Parameterized Complexity of Independent Set in H-Free Graphs. 2360-2394
Volume 82, Number 9, September 2020
- Manouchehr Zaker:
A New Vertex Coloring Heuristic and Corresponding Chromatic Number. 2395-2414 - Ziyun Huang, Jinhui Xu:
An Efficient Sum Query Algorithm for Distance-Based Locally Dominating Functions. 2415-2431 - Fedor V. Fomin, Petr A. Golovach, Jean-Florent Raymond:
On the Tractability of Optimization Problems on H-Graphs. 2432-2473 - Refael Hassin, R. Ravi, F. Sibel Salman, Danny Segev:
The Approximability of Multiple Facility Location on Directed Networks with Random Arc Failures. 2474-2501 - Yuichi Nagata, Shinji Imahori:
An Efficient Exhaustive Search Algorithm for the Escherization Problem. 2502-2534 - Akira Matsubayashi:
A $3+\varOmega (1)$ Lower Bound for Page Migration. 2535-2563 - Jawaherul Md. Alam, Michael A. Bekos, Martin Gronemann, Michael Kaufmann, Sergey Pupyrev:
Queue Layouts of Planar 3-Trees. 2564-2585 - Rémy Belmonte, Tesshu Hanaka, Michael Lampis, Hirotaka Ono, Yota Otachi:
Independent Set Reconfiguration Parameterized by Modular-Width. 2586-2605 - Zhao An, Qilong Feng, Iyad Kanj, Ge Xia:
The Complexity of Tree Partitioning. 2606-2643 - Danny Hermelin, George Manoussakis, Michael L. Pinedo, Dvir Shabtay, Liron Yedidsion:
Parameterized Multi-Scenario Single-Machine Scheduling Problems. 2644-2667 - Robert Chiang, Kanstantsin Pashkovich:
On the Approximability of the Stable Matching Problem with Ties of Size Two. 2668-2686 - Krzysztof Turowski, Abram Magner, Wojciech Szpankowski:
Compression of Dynamic Graphs Generated by a Duplication Model. 2687-2707
Volume 82, Number 10, October 2020
- Andreas Gemsa, Benjamin Niedermann, Martin Nöllenburg:
A Unified Model and Algorithms for Temporal Map Labeling. 2709-2736 - Brian Brubach, Karthik Abinav Sankararaman, Aravind Srinivasan, Pan Xu:
Online Stochastic Matching: New Algorithms and Bounds. 2737-2783 - Harel Yedidsion, Stav Ashur, Aritra Banik, Paz Carmi, Matthew J. Katz, Michael Segal:
Sensor Network Topology Design and Analysis for Efficient Data Gathering by a Mobile Mule. 2784-2808 - Ching-Chi Lin, Keng-Chu Ku, Chan-Hung Hsu:
Paired-Domination Problem on Distance-Hereditary Graphs. 2809-2840 - Konrad K. Dabrowski, Carl Feghali, Matthew Johnson, Giacomo Paesani, Daniël Paulusma, Pawel Rzazewski:
On Cycle Transversals and Their Connected Variants in the Absence of a Small Linear Forest. 2841-2866 - Julien Bensmail, Dorian Mazauric, Fionn Mc Inerney, Nicolas Nisse, Stéphane Pérennes:
Sequential Metric Dimension. 2867-2901 - Diptapriyo Majumdar, M. S. Ramanujan, Saket Saurabh:
On the Approximate Compressibility of Connected Vertex Cover. 2902-2926 - Argyrios Deligkas, John Fearnley, Paul G. Spirakis:
Lipschitz Continuity and Approximate Equilibria. 2927-2954 - Roland Glück, Dominik Köppl:
Computational Aspects of Ordered Integer Partitions with Bounds. 2955-2984 - Giordano Da Lozzo, Giuseppe Di Battista, Fabrizio Frati, Maurizio Patrignani, Vincenzo Roselli:
Upward Planar Morphs. 2985-3017 - Édouard Bonnet, Sergio Cabello, Bojan Mohar, Hebert Pérez-Rosés:
The Inverse Voronoi Problem in Graphs I: Hardness. 3018-3040 - An Zhang, Yong Chen, Zhi-Zhong Chen, Guohui Lin:
Improved Approximation Algorithms for Path Vertex Covers in Regular Graphs. 3041-3064 - Special Issue on Computing and Combinatorics. 3065
- Mingyu Xiao, Hiroshi Nagamochi:
Characterizing Star-PCGs. 3066-3090 - Shi Li, Jinhui Xu, Minwei Ye:
Approximating Global Optimum for Probabilistic Truth Discovery. 3091-3116