default search action
Algorithmica, Volume 81
Volume 81, Number 1, January 2019
- Susanne Albers, Achim Passen:
New Online Algorithms for Story Scheduling in Web Advertising. 1-25 - Neeldhara Misra, Fahad Panolan
, Ashutosh Rai, Venkatesh Raman, Saket Saurabh:
Parameterized Algorithms for Max Colorable Induced Subgraph Problem on Perfect Graphs. 26-46 - Amir Carmel
On Almost Monge All Scores Matrices. 47-68 - Therese Biedl, Timothy M. Chan, Stephanie Lee, Saeed Mehrabi, Fabrizio Montecchiani
Guarding Orthogonal Art Galleries with Sliding k-Transmitters: Hardness and Approximation. 69-97 - Julien Lesca
The Fair OWA One-to-One Assignment Problem: NP-Hardness and Polynomial Time Special Cases. 98-123 - Eleftherios Anastasiadis, Xiaotie Deng
Network Pollution Games. 124-166 - Tomonari Kitahara, Noriyoshi Sukegawa
A Simple Projection Algorithm for Linear Programming Problems. 167-178 - Harry Buhrman, Leen Torenvliet, Falk Unger, Nikolai K. Vereshchagin
Sparse Selfreducible Sets and Nonuniform Lower Bounds. 179-200 - Robert Ganian, Martin Kronegger, Andreas Pfandler, Alexandru Popa
Parameterized Complexity of Asynchronous Border Minimization. 201-223 - Cédric Bentz:
An FPT Algorithm for Planar Multicuts with Sources and Sinks on the Outer Face. 224-237 - Yoann Dieudonné
Impact of Knowledge on Election Time in Anonymous Networks. 238-288 - Joseph S. B. Mitchell, Valentin Polishchuk, Mikko Sysikaski, Haitao Wang
An Optimal Algorithm for Minimum-Link Rectilinear Paths in Triangulated Rectilinear Domains. 289-316 - Evangelos Bampas
Linear Search by a Pair of Distinct-Speed Robots. 317-342 - Takehiro Ito, Naonori Kakimura, Naoyuki Kamiyama, Yusuke Kobayashi, Yoshio Okamoto:
Minimum-Cost b-Edge Dominating Sets on Trees. 343-366 - Marc Bury, Elena Grigorescu, Andrew McGregor, Morteza Monemizadeh, Chris Schwiegelshohn
Structural Results on Matching Estimation with Applications to Streaming. 367-392 - Danny Segev
Assortment Planning with Nested Preferences: Dynamic Programming with Distributions as States? 393-417 - Koyo Hayashi, Satoru Iwata:
Correction to: Counting Minimum Weight Arborescences. 418
Volume 81, Number 2, February 2019
- Jiong Guo, Danny Hermelin:
Foreword: Special Issue on Parameterized and Exact Computation. 419-420 - Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen:
Subexponential-Time Algorithms for Maximum Independent Set in $$P_t$$ P t -Free and Broom-Free Graphs. 421-438 - Serge Gaspers, Joachim Gudmundsson
Turbocharging Treewidth Heuristics. 439-475 - Arne Meier
Backdoors for Linear Temporal Logic. 476-496 - Michal Wlodarczyk
Clifford Algebras Meet Tree Decompositions. 497-518 - Kitty Meeks
Randomised Enumeration of Small Witnesses Using a Decision Oracle. 519-540 - Cornelius Brand
Fine-Grained Dichotomies for the Tutte Plane and Boolean #CSP. 541-556 - Archontia C. Giannopoulou, Michal Pilipczuk
Cutwidth: Obstructions and Algorithmic Aspects. 557-588 - Carola Doerr
Preface to the Special Issue on Theory of Genetic and Evolutionary Computation. 589-592 - Benjamin Doerr, Christian Gießen, Carsten Witt
The (1+λ) Evolutionary Algorithm with Self-Adjusting Mutation Rate. 593-631 - Carsten Witt
Upper Bounds on the Running Time of the Univariate Marginal Distribution Algorithm on OneMax. 632-667 - Duc-Cuong Dang
Level-Based Analysis of the Univariate Marginal Distribution Algorithm. 668-702 - Benjamin Doerr, Carola Doerr
Solving Problems with Unknown Solution Length at Almost No Extra Cost. 703-748 - Chao Qian, Chao Bian, Wu Jiang, Ke Tang:
Running Time Analysis of the ( $$1+1$$ 1 + 1 )-EA for OneMax and LeadingOnes Under Bit-Wise Noise. 749-795 - Tomas Gavenciak
Sorting by Swaps with Noisy Comparisons. 796-827 - Feng Shi
Reoptimization Time Analysis of Evolutionary Algorithms on Linear Functions Under Dynamic Uniform Constraints. 828-857 - Samadhi Nallaperuma, Pietro S. Oliveto, Jorge Pérez Heredia
On the Analysis of Trajectory-Based Search Algorithms: When is it Beneficial to Reject Improvements? 858-885 - Benjamin Doerr, Philipp Fischbeck
Island Models Meet Rumor Spreading. 886-915
Volume 81, Number 3, March 2019
- Marcin Pilipczuk
Edge Bipartization Faster than $$2^k$$ 2 k. 917-966 - Surender Baswana, Keerti Choudhary
An Efficient Strongly Connected Components Algorithm in the Fault Tolerant Model. 967-985 - Mathieu Liedloff, Pedro Montealegre
Beyond Classes of Graphs with "Few" Minimal Separators: FPT Results Through Potential Maximal Cliques. 986-1005 - Babak Behsaz, Zachary Friggstad, Mohammad R. Salavatipour
Approximation Algorithms for Min-Sum k-Clustering and Balanced k-Median. 1006-1030 - Andreas Emil Feldmann
Fixed-Parameter Approximations for k-Center Problems in Low Highway Dimension Graphs. 1031-1052 - T. Karthick, Frédéric Maffray
Polynomial Cases for the Vertex Coloring Problem. 1053-1074 - Zachary Friggstad, Mohsen Rezapour
LP-Based Approximation Algorithms for Facility Location in Buy-at-Bulk Network Design. 1075-1095 - Austin Halper, Miguel A. Mosteiro
Station Assignment with Reallocation. 1096-1125 - Yann Disser, Stefan Kratsch, Manuel Sorge:
The Minimum Feasible Tileset Problem. 1126-1151 - Spyros Angelopoulos, Reza Dorrigiv, Alejandro López-Ortiz:
On the Separation and Equivalence of Paging Strategies and Other Online Algorithms. 1152-1179 - Frank Kammer, Dieter Kratsch, Moritz Laudahn:
Space-Efficient Biconnected Components and Recognition of Outerplanar Graphs. 1180-1204 - Artur Czumaj, Argyrios Deligkas
Distributed Methods for Computing Approximate Equilibria. 1205-1231 - Mourad Baïou, Francisco Barahona
Faster Algorithms for Security Games on Matroids. 1232-1246 - Piotr Berman, Meiram Murzabulatov
The Power and Limitations of Uniform Samples in Testing Properties of Figures. 1247-1266 - Fahad Panolan
Parameterized Algorithms for List K-Cycle. 1267-1287 - David G. Harris:
Deterministic Parallel Algorithms for Bilinear Objective Functions. 1288-1318
Volume 81, Number 4, April 2019
- Luis Barba, Jean Cardinal, Matias Korman, Stefan Langerman, André van Renssen
Dynamic Graph Coloring. 1319-1341 - Marthe Bonamy, Konrad K. Dabrowski
Independent Feedback Vertex Set for P5-Free Graphs. 1342-1369 - Simon Gog
Fixed Block Compression Boosting in FM-Indexes: Theory and Practice. 1370-1391 - Prosenjit Bose, Rolf Fagerberg, André van Renssen
On Plane Constrained Bounded-Degree Spanners. 1392-1415 - George B. Mertzios, Othon Michail, Paul G. Spirakis:
Temporal Network Optimization Subject to Connectivity Constraints. 1416-1449 - Dirk Sudholt
On the Choice of the Update Strength in Estimation-of-Distribution Algorithms and Ant Colony Optimization. 1450-1489 - Pavel Klavík
On the Classes of Interval Graphs of Limited Nesting and Count of Lengths. 1490-1511 - Ahmad Biniaz, Prosenjit Bose, Kimberly Crosbie, Jean-Lou De Carufel, David Eppstein, Anil Maheshwari, Michiel H. M. Smid:
Maximum Plane Trees in Multipartite Geometric Graphs. 1512-1534 - Pietro Cenciarelli, Daniele Gorla
A Polynomial-Time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs. 1535-1560 - Michael J. Bannister, William E. Devanny, Vida Dujmovic, David Eppstein, David R. Wood
Track Layouts, Layered Path Decompositions, and Leveled Planarity. 1561-1583 - Robert Bredereck, Vincent Froese, Marcel Koseler, Marcelo Garlet Millani, André Nichterlein
A Parameterized Algorithmics Framework for Degree Sequence Completion Problems in Directed Graphs. 1584-1614 - Valentin Garnero, Christophe Paul, Ignasi Sau
Explicit Linear Kernels for Packing Problems. 1615-1656 - Eduard Eiben
Counting Linear Extensions: Parameterizations by Treewidth. 1657-1683 - Sushmita Gupta, Sanjukta Roy
Parameterized Algorithms and Kernels for Rainbow Matching. 1684-1698 - Clément Carbonnel
On Singleton Arc Consistency for CSPs Defined by Monotone Patterns. 1699-1727 - Masoud Seddighin
Expand the Shares Together: Envy-Free Mechanisms with a Small Number of Cuts. 1728-1755
Volume 81, Number 5, May 2019
- Argyrios Deligkas
Binary Search in Graphs Revisited. 1757-1780 - Niv Buchbinder, Danny Segev
Online Algorithms for Maximum Cardinality Matching with Edge Arrivals. 1781-1799 - Mong-Jen Kao
O(f) Bi-criteria Approximation for Capacitated Covering with Hard Capacities. 1800-1817 - Franz J. Brandenburg:
Characterizing and Recognizing 4-Map Graphs. 1818-1843 - Viresh Patel, Guus Regts:
Computing the Number of Induced Copies of a Fixed Graph in a Bounded Degree Graph. 1844-1858 - Elisabet Burjons
The k-Server Problem with Advice in d Dimensions and on the Sphere. 1859-1880 - Lena Schlipf
Edge-Orders. 1881-1900 - Arnaud Casteigts
Deterministic Leader Election Takes Θ(D+log n) Bit Rounds. 1901-1920 - Xiaocheng Hu, Cheng Sheng, Yufei Tao
Building an Optimal Point-Location Structure in O( sort (n)) I/Os. 1921-1937 - Joan Boyar
Online Dominating Set. 1938-1964 - Zengfeng Huang
Dynamic Graph Stream Algorithms in o(n) Space. 1965-1987 - Shay Golan
Streaming Pattern Matching with d Wildcards. 1988-2015 - Till Fluschnik, Christian Komusiewicz, George B. Mertzios, André Nichterlein, Rolf Niedermeier, Nimrod Talmon:
When Can Graph Hyperbolicity be Computed in Linear Time? 2016-2045 - Michael A. Bekos
On Smooth Orthogonal and Octilinear Drawings: Relations, Complexity and Kandinsky Drawings. 2046-2071 - Ran Ben-Basat, Gil Einziger
Succinct Summing over Sliding Windows. 2072-2091 - Oguz Kaya
Computing Dense Tensor Decompositions with Optimal Dimension Trees. 2092-2121
Volume 81, Number 6, June 2019
- Amihood Amir, Tsvi Kopelowitz, Avivit Levy
Mind the Gap! - Online Dictionary Matching with One Gap. 2123-2157 - Tsuyoshi Ito, Stacey Jeffery
Approximate Span Programs. 2158-2195 - Patrizio Angelini
Hierarchical Partial Planarity. 2196-2221 - Zengfeng Huang
Randomized Algorithms for Tracking Distributed Count, Frequencies, and Ranks. 2222-2243 - Ashwinkumar Badanidiyuru, Shahar Dobzinski, Sigal Oren:
Optimization with Demand Oracles. 2244-2269 - Ron Y. Pinter, Hadas Shachnai, Meirav Zehavi:
Improved Parameterized Algorithms for Network Query Problems. 2270-2316 - Cecilia Bohler, Rolf Klein, Chih-Hung Liu
An Efficient Randomized Algorithm for Higher-Order Abstract Voronoi Diagrams. 2317-2345 - Haitao Wang
Covering Uncertain Points in a Tree. 2346-2376 - Khaled M. Elbassioni
A Multiplicative Weight Updates Algorithm for Packing and Covering Semi-infinite Linear Programs. 2377-2429 - Danny Z. Chen, Haitao Wang
Computing L1 Shortest Paths Among Polygonal Obstacles in the Plane. 2430-2483 - Patrizio Angelini
Clustered Planarity with Pipes. 2484-2526 - Patrizio Angelini
Universal Slope Sets for 1-Bend Planar Drawings. 2527-2556 - Ágnes Cseh
New and Simple Algorithms for Stable Flow Problems. 2557-2591 - Samir Khuller, Sheng Yang
Revisiting Connected Dominating Sets: An Almost Optimal Local Information Algorithm. 2592-2605 - Robert Ganian, N. S. Narayanaswamy, Sebastian Ordyniak
On the Complexity Landscape of Connected f-Factor Problems. 2606-2632 - Tomasz Kociumaka
Longest Common Substring with Approximately k Mismatches. 2633-2652
Volume 81, Number 7, July 2019
- Hugo Gilbert
Optimizing a Generalized Gini Index in Stable Marriage Problems: NP-Hardness, Approximation and a Polynomial Time Special Case. 2653-2681 - Kevin Buchin
Region-Based Approximation of Probability Distributions (for Visibility Between Imprecise Points Among Obstacles). 2682-2715 - Pierre-Louis Giscard
A General Purpose Algorithm for Counting Simple Cycles and Simple Paths of Any Length. 2716-2737 - Florian Brandl
Two Problems in Max-Size Popular Matchings. 2738-2764 - K. Subramani
A Polynomial Time Algorithm for Read-Once Certification of Linear Infeasibility in UTVPI Constraints. 2765-2794 - Petr A. Golovach
Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2. 2795-2828 - Eunjin Oh, Hee-Kap Ahn
A New Balanced Subdivision of a Simple Polygon for Time-Space Trade-Off Algorithms. 2829-2856 - Amihood Amir, Avivit Levy
Can We Recover the Cover? 2857-2875 - Shaojiang Wang, Kun He, Yicheng Pan
Rectangle Transformation Problem. 2876-2898 - Lucila M. S. Bento
Full Characterization of a Class of Graphs Tailored for Software Watermarking. 2899-2916 - Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Michele Scquizzato
A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line. 2917-2933 - Mark de Berg
The Homogeneous Broadcast Problem in Narrow and Wide Strips I: Algorithms. 2934-2962 - Mark de Berg
The Homogeneous Broadcast Problem in Narrow and Wide Strips II: Lower Bounds. 2963-2990 - Marvin Künnemann, Daniel Moeller, Ramamohan Paturi, Stefan Schneider
Subquadratic Algorithms for Succinct Stable Matching. 2991-3024 - Ishai Kones, Asaf Levin
A Unified Framework for Designing EPTAS for Load Balancing on Parallel Machines. 3025-3046 - Édouard Bonnet, Pawel Rzazewski
Optimality Program in Segment and String Graphs. 3047-3073 - Tomasz Kociumaka
Correction to: Longest Common Substring with Approximately k Mismatches. 3074
Volume 81, Number 8, August 2019
- Timothy M. Chan
Faster Approximate Diameter and Distance Oracles in Planar Graphs. 3075-3098 - Mourad Baïou, Francisco Barahona
An Algorithm to Compute the Nucleolus of Shortest Path Games. 3099-3113 - Robert T. Schweller, Andrew Winslow, Tim Wylie:
Nearly Constant Tile Complexity for any Shape in Two-Handed Tile Assembly. 3114-3135 - Yakov Babichenko, Yuval Emek, Michal Feldman, Boaz Patt-Shamir, Ron Peretz, Rann Smorodinsky:
Stable Secretaries. 3136-3161 - Tobias Maier
Dynamic Space Efficient Hashing. 3162-3185 - Maria Chudnovsky
Approximately Coloring Graphs Without Long Induced Paths. 3186-3199 - Rajesh Chitnis
A Tight Lower Bound for Planar Steiner Orientation. 3200-3216 - Dmitriy Katz, Baruch Schieber, Hadas Shachnai:
Flexible Resource Allocation to Interval Jobs. 3217-3244
Volume 81, Number 9, September 2019
- Pratish Datta
Constrained Pseudorandom Functions for Turing Machines Revisited: How to Achieve Verifiability and Key Delegation. 3245-3390 - Spyros Angelopoulos, Giorgio Lucarelli
Primal-Dual and Dual-Fitting Analysis of Online Scheduling Algorithms for Generalized Flow-Time Problems. 3391-3421 - Piotr Krysta, David F. Manlove
Size Versus Truthfulness in the House Allocation Problem. 3422-3463 - Emilio Di Giacomo, Giuseppe Liotta, Maurizio Patrignani, Ignaz Rutter
NodeTrix Planarity Testing with Small Clusters. 3464-3493 - Luis Barba, Malte Milatz
The Complexity of Optimization on Grids. 3494-3518 - Timothy M. Chan
Two Approaches to Building Time-Windowed Geometric Data Structures. 3519-3533 - Guru Prakash Arumugam, John Augustine, Mordecai J. Golin
Minmax Regret k-Sink Location on a Dynamic Path Network with Uniform Capacities. 3534-3585 - Geevarghese Philip, Varun Rajan, Saket Saurabh, Prafullkumar Tale
Subset Feedback Vertex Set in Chordal and Split Graphs. 3586-3629 - Pawel Gawrychowski
Tight Tradeoffs for Real-Time Approximation of Longest Palindromes in Streams. 3630-3654 - Tomasz Kociumaka
Deleting Vertices to Graphs of Bounded Genus. 3655-3691 - David Bryant
An O(n log n) Time Algorithm for Computing the Path-Length Distance Between Trees. 3692-3706 - Megha Khosla
A Faster Algorithm for Cuckoo Insertion and Bipartite Matching in Large Graphs. 3707-3724 - Antonios Antoniadis
A Fully Polynomial-Time Approximation Scheme for Speed Scaling with a Sleep State. 3725-3745 - Kyle Fox, Sungjin Im, Janardhan Kulkarni, Benjamin Moseley:
Non-clairvoyantly Scheduling to Minimize Convex Functions. 3746-3764 - Eldar Fischer, Oded Lachish
Improving and Extending the Testing of Distributions for Shape-Restricted Properties. 3765-3802 - R. Krithika
The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue. 3803-3841
Volume 81, Number 10, October 2019
- Editor's Note: Special Issue on Parameterized and Exact Computation. 3843
- Radu Curticapean, Holger Dell, Fedor V. Fomin
A Fixed-Parameter Perspective on #BIS. 3844-3864 - Bart M. P. Jansen
Optimal Data Reduction for Graph Coloring Using Low-Degree Polynomials. 3865-3889 - Édouard Bonnet, Nick Brettell
Generalized Feedback Vertex Set Problems on Bounded-Treewidth Graphs: Chordality is the Key to Single-Exponential Parameterized Algorithms. 3890-3935 - Bart M. P. Jansen, Marcin Pilipczuk, Marcin Wrochna
Turing Kernelization for Finding Long Paths in Graph Classes Excluding a Topological Minor. 3936-3967 - Lech Duraj
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence. 3968-3992 - Nikhil Bansal, Parinya Chalermsook, Bundit Laekhanukit, Danupon Nanongkai, Jesper Nederlof
New Tools and Connections for Exponential-Time Approximation. 3993-4009 - Andreas Björklund, Petteri Kaski, Ryan Williams:
Generalized Kakeya sets for polynomial evaluation and faster computation of fermionants. 4010-4028 - Nikolai Karpov, Marcin Pilipczuk
An Exponential Lower Bound for Cut Sparsifiers in Planar Graphs. 4029-4042 - Marin Bougeret
How Much Does a Treedepth Modulator Help to Obtain Polynomial Kernels Beyond Sparse Graphs? 4043-4068 - Preface: Special Issue on WADS 2017. 4069
- Sebastian Brandt
Approximating Small Balanced Vertex Separators in Almost Linear Time. 4070-4097 - Philip Dasler
Modular Circulation and Applications to Traffic Management. 4098-4117 - Ziyun Huang
A Faster Algorithm for Truth Discovery via Range Cover. 4118-4133 - Klaus Jansen, Marten Maack
An EPTAS for Scheduling on Unrelated Machines of Few Different Types. 4134-4164
Volume 81, Numbers 11-12, November 2019
- Yixin Cao, Jianer Chen:
Preface to the Special Issue on Computing and Combinatorics. 4165-4166 - Zhi-Zhong Chen, Guohui Lin
Approximation Algorithms for the Maximum Weight Internal Spanning Tree Problem. 4167-4199 - Yuval Filmus, Hamed Hatami, Yaqiao Li
Information Complexity of the AND Function in the Two-Party and Multi-party Settings. 4200-4237 - Stanley P. Y. Fung
Optimal Online Two-Way Trading with Bounded Number of Transactions. 4238-4257 - Hoàng-Oanh Le
Hardness and Structural Results for Half-Squares of Restricted Tree Convex Bipartite Graphs. 4258-4274 - Sumedh Tirodkar, Sundar Vishwanathan:
Maximum Matching on Trees in the Online Preemptive and the Incremental Graph Models. 4275-4292
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2024-11-22 19:33 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: