default search action
Algorithmica, Volume 80
Volume 80, Number 1, January 2018
- Franz J. Brandenburg:
Recognizing Optimal 1-Planar Graphs in Linear Time. 1-28 - Rémy Belmonte, Yota Otachi
, Pascal Schweitzer
Induced Minor Free Graphs: Isomorphism and Clique-Width. 29-47 - Fidaa Abed
Near-Optimal Asymmetric Binary Matrix Partitions. 48-72 - Katharina T. Huber, Guillaume E. Scholz:
Beyond Representing Orthology Relations by Trees. 73-103 - Victor A. Campos, Ana Silva
Edge-b-Coloring Trees. 104-115 - Eun Jung Kim
An FPT 2-Approximation for Tree-Cut Decomposition. 116-135 - Peter Floderus, Jesper Jansson
3D Rectangulations and Geometric Matrix Multiplication. 136-154 - Martin Böhm
Colored Bin Packing: Online Algorithms and Lower Bounds. 155-184 - Ashwin Arulselvan, Ágnes Cseh
Matchings with Lower Quotas: Algorithms and Complexity. 185-208 - Frédéric Giroire
On the Complexity of Compressing Two Dimensional Routing Tables with Order. 209-233 - Stefan Felsner, Alexander Pilz
Ham-Sandwich Cuts for Abstract Order Types. 234-257 - Ildikó Schlotter
A Connection Between Sports and Matroids: How Many Teams Can We Beat? 258-278 - Sariel Har-Peled
Robust Proximity Search for Balls Using Sublinear Space. 279-299 - Ghurumuruhan Ganesan:
Stretch and Diameter in Random Geometric Graphs. 300-330 - Abram Magner, Wojciech Szpankowski:
Profiles of PATRICIA Tries. 331-397 - Peng Zhang, Bin Fu, Linqing Tang:
Simpler and Better Approximation Algorithms for the Unweighted Minimum Label s-t Cut Problem. 398-409 - Bert Besser, Matthias Poloczek
Erratum to: Greedy Matching: Guarantees and Limitations. 410-413
Volume 80, Number 2, February 2018
- Martin Milanic, Irena Penev
Stable Sets in {ISK4, wheel}-Free Graphs. 415-447 - Anil Maheshwari, Subhas C. Nandy, Drimit Pattanayak, Sasanka Roy, Michiel H. M. Smid:
Geometric Path Problems with Violations. 448-471 - Boaz Farbstein, Asaf Levin
Discounted Reward TSP. 472-495 - Carl Barton
Crochemore's Partitioning on Weighted Strings and Applications. 496-514 - Mohammad Ali Abam
Spanners for Geodesic Graphs and Visibility Graphs. 515-529 - Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part I: Stemless TAP. 530-559 - Gábor Ivanyos
Polynomial Interpolation and Identity Testing from High Powers Over Finite Fields. 560-575 - Baruch Schieber, Hadas Shachnai, Gal Tamir, Tami Tamir:
A Theory and Algorithms for Combinatorial Reoptimization. 576-607 - Joseph Cheriyan, Zhihan Gao:
Approximating (Unweighted) Tree Augmentation via Lift-and-Project, Part II. 608-651 - Vladimir Braverman, Zaoxing Liu
New Bounds for the CLIQUE-GAP Problem Using Graph Decomposition Theory. 652-667 - Maryam Aliakbarpour
Sublinear-Time Algorithms for Counting Star Subgraphs via Edge Sampling. 668-697 - Wing-Kai Hon
Dictionary Matching with a Bounded Gap in Pattern or in Text. 698-713 - Petr A. Golovach
Output-Polynomial Enumeration on Graphs of Bounded (Local) Linear MIM-Width. 714-741 - Eduard Eiben, Robert Ganian
Solving Problems on Graphs of High Rank-Width. 742-771 - Bhaskar DasGupta
Effect of Gromov-Hyperbolicity Parameter on Cuts and Expansions in Graphs and Some Algorithmic Implications. 772-800 - Chih-Hung Liu
Minimizing the Diameter of a Spanning Tree for Imprecise Points. 801-826
Volume 80, Number 3, March 2018
- Evangelos Kranakis
Guest Editorial: Special Issue on Theoretical Informatics. 827-829 - Haim Kaplan, Wolfgang Mulzer
Routing in Unit Disk Graphs. 830-848 - Mercè Claverol
Stabbing Circles for Sets of Segments in the Plane. 849-884 - Moses Ganardi, Danny Hucke, Markus Lohrey, Eric Noeth:
Tree Compression Using String Grammars. 885-917 - Andreas Wiese
Independent Set of Convex Polygons: From $$n^{\epsilon }$$ n ϵ to $$1+\epsilon $$ 1 + ϵ via Shrinking. 918-934 - Prosenjit Bose, Darryl Hill
Improved Spanning Ratio for Low Degree Plane Spanners. 935-976 - David Eppstein, Philipp Kindermann
On the Planar Split Thickness of Graphs. 977-994 - Alice Paul, Matthias Poloczek
Simple Approximation Algorithms for Balanced MAX 2SAT. 995-1012 - Marek Chrobak, Kevin P. Costello
Faster Information Gathering in Ad-Hoc Radio Tree Networks. 1013-1040 - Cristina G. Fernandes
Improved Approximation Algorithms for Capacitated Fault-Tolerant k-Center. 1041-1072 - Kamal Al-Bawani
Comparison-Based Buffer Management in QoS Switches. 1073-1092
Volume 80, Number 4, April 2018
- Jaroslaw Byrka
An Improved Approximation Algorithm for Knapsack Median Using Sparsification. 1093-1114 - George Christodoulou
On the Efficiency of All-Pay Mechanisms. 1115-1145 - Fedor V. Fomin
Algorithms Parameterized by Vertex Cover and Modular Width, Through Potential Maximal Cliques. 1146-1169 - Aparna Das, Krzysztof Fleszar
Approximating the Generalized Minimum Manhattan Network Problem. 1170-1190 - Wiebke Höhn, Julián Mestre, Andreas Wiese
How Unsplittable-Flow-Covering Helps Scheduling with Job-Dependent Cost Functions. 1191-1213 - Thomas Bläsius
Simultaneous Embedding: Edge Orderings, Relative Positions, Cutvertices. 1214-1277 - David Eppstein, Daniel S. Hirschberg:
From Discrepancy to Majority. 1278-1297 - Ulrich Faigle, Walter Kern, Britta Peis:
Greedy Oriented Flows. 1298-1314 - Xiaocheng Hu, Yufei Tao
Semi-Group Range Sum Revisited: Query-Space Lower Bound Tightened. 1315-1329 - Dimitris Chatzidimitriou, Jean-Florent Raymond
An O(log OPT)-Approximation for Covering and Packing Minor Models of θr. 1330-1356 - Klaus Jansen, Kati Land
Estimating the Makespan of the Two-Valued Restricted Assignment Problem. 1357-1382 - Cameron T. Chalk, Eric Martinez, Robert T. Schweller, Luis Vega, Andrew Winslow, Tim Wylie:
Optimal Staged Self-Assembly of General Shapes. 1383-1409
Volume 80, Number 5, May 2018
- Donglei Du
Editorial: Special Issue on Computing and Combinatorics. 1411 - Peng Zhang, Yao Xu
Improved Approximation Algorithms for the Maximum Happy Vertices and Edges Problems. 1412-1438 - Anup Bhattacharya, Davis Issac
Sampling in Space Restricted Settings. 1439-1458 - Daniel König, Markus Lohrey:
Evaluation of Circuits Over Nilpotent and Polycyclic Groups. 1459-1492 - Benjamin Niedermann
An Algorithmic Framework for Labeling Network Maps. 1493-1533 - Zhenbo Wang, Xin Han, György Dósa, Zsolt Tuza:
A General Bin Packing Game: Interest Taken into Account. 1534-1555 - Shouwei Li, Christine Markarian
Towards Flexible Demands in Online Leasing Problems. 1556-1574 - Timo Kötzing, Dirk Sudholt:
Preface to the Special Issue on Theory of Genetic and Evolutionary Computation. 1575-1578 - Carola Doerr
The (1+1) Elitist Black-Box Complexity of LeadingOnes. 1579-1603 - Pietro S. Oliveto
How to Escape Local Optima in Black Box Optimisation: When Non-elitism Outperforms Elitism. 1604-1633 - Andrei Lissovoi, Carsten Witt
The Impact of a Sparse Migration Topology on the Runtime of Island Models in Dynamic Optimization. 1634-1657 - Benjamin Doerr, Carola Doerr
Optimal Static and Self-Adjusting Parameter Choices for the (1+(λ, λ)) Genetic Algorithm. 1658-1709 - Christian Gießen, Carsten Witt
Optimal Mutation Rates for the (1+λ) EA on OneMax Through Asymptotically Tight Drift Analysis. 1710-1731 - Benjamin Doerr, Carola Doerr
Static and Self-Adjusting Mutation Strengths for Multi-valued Decision Variables. 1732-1768
Volume 80, Number 6, June 2018
- Zaixin Lu, Donghyun Kim:
Guest Editorial: Special Issue on Combinatorial Optimization and Applications. 1769-1770 - Mathias Weller, Annie Chateau
Scaffolding Problems Revisited: Complexity, Approximation and Fixed Parameter Tractable Algorithms, and Some Special Cases. 1771-1803 - Gennaro Cordasco
Discovering Small Target Sets in Social Networks: A Fast and Effective Algorithm. 1804-1833 - Yuichi Asahiro, Yuya Doi, Eiji Miyano
Optimal Approximation Algorithms for Maximum Distance-Bounded Subgraph Problems. 1834-1856 - Jessica A. Enright, Kitty Meeks
Deleting Edges to Restrict the Size of an Epidemic: A New Application for Treewidth. 1857-1889 - Cristina Bazgan, Janka Chlebíková
Structural and Algorithmic Properties of 2-Community Structures. 1890-1908 - David Furcy, Scott M. Summers:
Optimal Self-Assembly of Finite Shapes at Temperature 1 in 3D. 1909-1963 - Minghui Jiang
Trees, Paths, Stars, Caterpillars and Spiders. 1964-1982
Volume 80, Number 7, July 2018
- Travis Gagie
Guest Editorial: Special Issue on Compact Data Structures. 1983-1985 - Alberto Policriti
LZ77 Computation Based on the Run-Length Encoded BWT. 1986-2011 - Julian Arz, Johannes Fischer:
Lempel-Ziv-78 Compressed String Dictionaries. 2012-2047 - Johannes Fischer, Tomohiro I, Dominik Köppl
Lempel-Ziv Factorization Powered by Space Efficient Suffix Trees. 2048-2081 - Markus Lohrey, Sebastian Maneth, Carl Philipp Reh:
Constant-Time Tree Traversal and Subtree Equality Check for Grammar-Compressed Trees. 2082-2105 - Shahin Kamali:
Compact Representation of Graphs of Small Clique-Width. 2106-2131 - Seok-Hee Hong:
Editorial: Special Issue on Algorithms and Computation. 2132-2133 - Yasushi Kawase
Optimal Composition Ordering Problems for Piecewise Linear Functions. 2134-2159 - Hans L. Bodlaender
Degree-Constrained Orientation of Maximum Satisfaction: Graph Classes and Parameterized Complexity. 2160-2180 - T.-H. Hubert Chan, Zhihao Gavin Tang, Xiaowei Wu
On (1,ϵ)-Restricted Max-Min Fair Allocation Problem. 2181-2200 - Shahram Ghandeharizadeh, Sandy Irani
The Subset Assignment Problem for Data Placement in Caches. 2201-2220
Volume 80, Number 8, August 2018
- Samuel Fiorini, R. Krithika
Approximability of Clique Transversal in Perfect Graphs. 2221-2239 - Magnus Bordewich
Constructing Tree-Child Networks from Distance Matrices. 2240-2259 - Till Bruckdorfer, Stefan Felsner, Michael Kaufmann:
Planar Bus Graphs. 2260-2285 - Steven Chaplick
The Partial Visibility Representation Extension Problem. 2286-2323 - Thomas Bläsius, Tobias Friedrich, Anton Krohmer
Cliques in Hyperbolic Random Graphs. 2324-2344 - Emilio Di Giacomo, Walter Didimo, William S. Evans, Giuseppe Liotta, Henk Meijer, Fabrizio Montecchiani
Ortho-polygon Visibility Representations of Embedded Graphs. 2345-2383 - Vadim E. Levit
Complexity Results for Generating Subgraphs. 2384-2399 - Rinat Ben Avraham, Matthias Henze
Partial-Matching RMS Distance Under Translation: Combinatorics and Algorithms. 2400-2421 - Sander P. A. Alewijnse, Kevin Buchin
Model-Based Segmentation and Classification of Trajectories. 2422-2452 - Yun Deng, David Fernández-Baca:
Fast Compatibility Testing for Rooted Phylogenetic Trees. 2453-2477 - Hiroshi Hirai, Hiroyuki Namba:
Shortest (A+B)-Path Packing Via Hafnian. 2478-2491 - Christopher S. Martin, Mohammad R. Salavatipour
Minimizing Latency of Capacitated k-Tours. 2492-2511
Volume 80, Number 9, September 2018
- Fedor V. Fomin
Preface to Special Issue Dedicated to the 60th Birthday of Gregory Gutin. 2513-2515 - Editor's Note: Special Issue Dedicated to the 60th Birthday of Gregory Gutin. 2516
- Faisal N. Abu-Khzam, Cristina Bazgan, Katrin Casel, Henning Fernau
Clustering with Lower-Bounded Sizes - A General Graph-Theoretic Framework. 2517-2550 - Sushmita Gupta, Sanjukta Roy
Stable Matching Games: Manipulation via Subgraph Isomorphism. 2551-2573 - Michael Etscheid, Matthias Mnich
Linear Kernels and Linear-Time Algorithms for Finding Large Cuts. 2574-2615 - Aritra Banik, Fahad Panolan
Fréchet Distance Between a Line and Avatar Point Set. 2616-2636 - R. Krithika
Dynamic Parameterized Problems. 2637-2655 - Édouard Bonnet, Tillmann Miltzow, Pawel Rzazewski
Complexity of Token Swapping and Its Variants. 2656-2682 - Diptapriyo Majumdar
Structural Parameterizations of Undirected Feedback Vertex Set: FPT Algorithms and Kernelization. 2683-2724
Volume 80, Number 10, October 2018
- Atsuki Nagao
A Moderately Exponential Time Algorithm for k-IBDD Satisfiability. 2725-2741 - Zahed Rahmati
A Clustering-Based Approach to Kinetic Closest Pair. 2742-2756 - Syed Mohammad Meesum, Saket Saurabh:
Rank Reduction of Oriented Graphs by Vertex and Edge Deletions. 2757-2776 - Riley Murray
Scheduling Distributed Clusters of Parallel Machines : Primal-Dual and LP-based Approximation Algorithms. 2777-2798 - Hassan AbouEisha
Upper Domination: Towards a Dichotomy Through Boundary Properties. 2799-2817 - Martijn van Ee, René Sitters:
The A Priori Traveling Repairman Problem. 2818-2833 - Emile Ziedan, Deepak Rajendraprasad
The Induced Separation Dimension of a Graph. 2834-2848 - Benjamin Grimmer
Dual-Based Approximation Algorithms for Cut-Based Network Connectivity Problems. 2849-2873 - Uriel Feige, Yael Hitron
The Ordered Covering Problem. 2874-2908 - Bernhard Bliem
Complexity of Secure Sets. 2909-2940 - Tim Nonner:
Clique Clustering Yields a PTAS for Max-Coloring Interval Graphs. 2941-2956 - Naoyuki Kamiyama:
A Note on Submodular Function Minimization with Covering Type Linear Constraints. 2957-2971
Volume 80, Number 11, November 2018
- Cristina G. Fernandes
Approximation Algorithms for the Max-Buying Problem with Limited Supply. 2973-2992 - Leo van Iersel, Steven Kelk, Georgios Stamoulis, Leen Stougie, Olivier Boes:
On Unrooted and Root-Uncertain Variants of Several Well-Known Phylogenetic Network Problems. 2993-3022 - Maitri Chakraborty, Alessia Milani, Miguel A. Mosteiro:
A Faster Exact-Counting Protocol for Anonymous Dynamic Networks. 3023-3049 - Paz Carmi, Lilach Chaitman-Yerushalmi
Bounded-Hop Communication Networks. 3050-3077 - Vincenzo Auletta
Metastability of Logit Dynamics for Coordination Games. 3078-3131 - Endre Boros, Khaled M. Elbassioni
Approximation Schemes for Stochastic Mean Payoff Games with Perfect Information and Few Random Positions. 3132-3157 - Wenchang Luo
Algorithms for Communication Scheduling in Data Gathering Network with Data Compression. 3158-3176 - Ahmad Biniaz, Prosenjit Bose
Spanning Trees in Multipartite Geometric Graphs. 3177-3191 - Peyman Afshani, Konstantinos Tsakalidis:
Optimal Deterministic Shallow Cuttings for 3-d Dominance Ranges. 3192-3206 - Philip Bille
Dynamic Relative Compression, Dynamic Partial Sums, and Substring Concatenation. 3207-3224 - Alok Baveja
Improved Bounds in Stochastic Matching and Optimization. 3225-3252 - Mark de Berg
Finding Pairwise Intersections Inside a Query Range. 3253-3269 - Takuro Fukunaga
Approximation Algorithms for Highly Connected Multi-dominating Sets in Unit Disk Graphs. 3270-3292 - Joan Boyar
Batch Coloring of Graphs. 3293-3315 - Boris Aronov
Data Structures for Halfplane Proximity Queries and Incremental Voronoi Diagrams. 3316-3334 - Jiawei Qian, Seeun William Umboh
Online Constrained Forest and Prize-Collecting Network Design. 3335-3364 - Raphael Reitzig, Sebastian Wild
Building Fences Straight and High: An Optimal Algorithm for Finding the Maximum Length You Can Cut k Times from Given Sticks. 3365-3396 - Karl Bringmann, Tobias Friedrich, Anton Krohmer
De-anonymization of Heterogeneous Random Graphs in Quasilinear Time. 3397-3427 - Ildikó Schlotter
Correction to: A Connection Between Sports and Matroids: How Many Teams Can We Beat? 3428-3430 - Aline Medeiros Saettler, Eduardo Sany Laber, Ferdinando Cicalese:
Correction to: Trading Off Worst and Expected Cost in Decision Tree Problems. 3431-3436
Volume 80, Number 12, December 2018
- Davide Bilò
Fault-Tolerant Approximate Shortest-Path Trees. 3437-3460 - Yasushi Kawase, Atsushi Miyauchi
The Densest Subgraph Problem with a Convex/Concave Size Function. 3461-3480 - Pål Grønås Drange, Michal Pilipczuk
A Polynomial Kernel for Trivially Perfect Editing. 3481-3524 - Carlo Comin
An Improved Upper Bound on Maximal Clique Listing via Rectangular Fast Matrix Multiplication. 3525-3562 - Susanne Albers, Dario Frascaria:
Quantifying Competitiveness in Paging with Locality of Reference. 3563-3596 - Pavel Dvorák
Parameterized Complexity of Length-bounded Cuts and Multicuts. 3597-3617 - Maria Chudnovsky
The Sandwich Problem for Decompositions and Almost Monotone Properties. 3618-3645 - Maurice Chandoo
Canonical Representations for Circular-Arc Graphs Using Flip Sets. 3646-3672 - Petra Berenbrink, Tom Friedetzky
Self-Stabilizing Balls and Bins in Batches - The Power of Leaky Bins. 3673-3703 - Ali Dehghan, Mohammad-Reza (Rafsanjani) Sadeghi
Not-All-Equal and 1-in-Degree Decompositions: Algorithmic Complexity and Applications. 3704-3727 - Meng He
Dynamic Path Queries in Linear Space. 3728-3765 - Amin Gheibi
Path Refinement in Weighted Regions. 3766-3802 - Facundo Mémoli, Anastasios Sidiropoulos, Vijay Sridhar
Quasimetric Embeddings and Their Applications. 3803-3824 - Imed Kacem
Approximation Schemes for Minimizing the Maximum Lateness on a Single Machine with Release Times Under Non-availability or Deadline Constraints. 3825-3843 - Saket Saurabh, Meirav Zehavi:
$$(k, n-k)$$ ( k , n - k ) -Max-Cut: An $$\mathcal{O}^*(2^p)$$ O ∗ ( 2 p ) -Time Algorithm and a Polynomial Kernel. 3844-3860 - Kamal Al-Bawani
Online Packet Scheduling for CIOQ and Buffered Crossbar Switches. 3861-3888 - Katherine Edwards
Fast Approximation Algorithms for p-Centers in Large $$\delta $$ δ -Hyperbolic Graphs. 3889-3907 - Koyo Hayashi, Satoru Iwata:
Counting Minimum Weight Arborescences. 3908-3919 - Eden Chlamtác
Lift-and-Project Methods for Set Cover and Knapsack. 3920-3942 - Andrzej Lingas, Mia Persson:
Extreme Witnesses and Their Applications. 3943-3957 - Editor's Note. 3958
- Yuan Xue, Boting Yang, Farong Zhong, Sandra Zilles:
The Fast Search Number of a Complete k-Partite Graph. 3959-3981
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-12-26 00:36 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: