×

ACM Transactions on Algorithms

Short Title: ACM Trans. Algorithms
Publisher: Association for Computing Machinery (ACM), New York, NY
ISSN: 1549-6325; 1549-6333/e
Online: https://dl.acm.org/loi/talg
Comments: Journal
Documents Indexed: 857 Publications (since 2005)
References Indexed: 65 Publications with 2,392 References.
all top 5

Authors

27 Saurabh, Saket
25 Lokshtanov, Daniel
14 Fomin, Fedor V.
14 Hajiaghayi, Mohammad Taghi
14 Marx, Dániel
13 Kortsarz, Guy
11 Agarwal, Pankaj Kumar
11 Tarjan, Robert Endre
10 Grandoni, Fabrizio
10 Pilipczuk, Michał
9 Chan, Timothy Moon-Yew
9 Cygan, Marek
9 Har-Peled, Sariel
9 Kaplan, Haim
9 Pelc, Andrzej
9 Pilipczuk, Marcin L.
9 Thorup, Mikkel
9 Zehavi, Meirav
9 Zwick, Uri
8 Bansal, Nikhil
8 Demaine, Erik D.
8 Halldórsson, Magnús Mar
8 Harris, David G.
8 Navarro, Gonzalo
8 Nutov, Zeev
8 Peleg, David
8 Solomon, Shay
8 Vassilevska Williams, Virginia
7 Chan, T.-H. Hubert
7 Elkin, Michael
7 Eppstein, David Arthur
7 Gupta, Anupam
7 Pettie, Seth
7 Salavatipour, Mohammad R.
7 Sharir, Micha
7 Sviridenko, Maxim I.
7 Yi, Ke
6 Alon, Noga
6 Aronov, Boris
6 Azar, Yossi
6 Chekuri, Chandra S.
6 Gabow, Harold N.
6 Gørtz, Inge Li
6 Khandekar, Rohit
6 Lewenstein, Moshe
6 Mozes, Shay
6 Munro, J. Ian
6 Nagarajan, Viswanath
6 Nederlof, Jesper
6 Panigrahi, Debmalya
6 Panolan, Fahad
6 Raman, Venkatesh
6 Roditty, Liam
6 Rosén, Adi
6 Rutter, Ignaz
6 Thilikos, Dimitrios M.
6 Weimann, Oren
6 Woodruff, David P.
6 Yuster, Raphael
6 Živný, Stanislav
5 Baswana, Surender
5 Cabello, Sergio
5 Cheng, Siu-Wing
5 Cormode, Graham
5 Czumaj, Artur
5 Even, Guy
5 Ferragina, Paolo
5 Klein, Philip N.
5 Korman, Amos
5 Mäkinen, Veli
5 Mathieu, Claire
5 Misra, Pranabendu
5 Muthukrishnan, S. Muthu
5 Naor, Joseph Seffi
5 Pruhs, Kirk R.
5 Ron, Dana
5 Schieber, Baruch
5 Shachnai, Hadas
5 Srinivasan, Aravind
5 Wahlström, Magnus
4 Abboud, Amir
4 Bille, Philip
4 Björklund, Andreas
4 Bläsius, Thomas
4 Borradaile, Glencora
4 Bringmann, Karl
4 Chan, Ho-Leung
4 Chrobak, Marek
4 de Berg, Mark Theodoor
4 Driemel, Anne
4 Farach-Colton, Martin
4 Feldman, Moran
4 Friggstad, Zachary
4 Georgiadis, Loukas
4 Goel, Ashish
4 Golovach, Petr A.
4 Grossi, Roberto
4 Gudmundsson, Joachim
4 Guha, Sudipto
4 Haeupler, Bernhard
...and 1,343 more Authors

Publications by Year

Citations contained in zbMATH Open

682 Publications have been cited 5,971 times in 4,462 Documents Cited by Year
Compressed representations of sequences and full-text indexes. Zbl 1321.68263
Ferragina, Paolo; Manzini, Giovanni; Mäkinen, Veli; Navarro, Gonzalo
183
2007
Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets. Zbl 1446.68046
Raman, Rajeev; Raman, Venkatesh; Satti, Srinivasa Rao
83
2007
Algorithmic construction of sets for \(k\)-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
77
2006
A \(4k^2\) kernel for feedback vertex set. Zbl 1300.05236
Thomassé, Stéphan
72
2010
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. Zbl 1300.90026
Clarkson, Kenneth L.
70
2010
Cache-oblivious algorithms. Zbl 1295.68236
Frigo, Matteo; Leiserson, Charles E.; Prokop, Harald; Ramachandran, Sridhar
67
2012
Faster parameterized algorithms using linear programming. Zbl 1398.68254
Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket
65
2014
Fully functional static and dynamic succinct trees. Zbl 1333.68084
Navarro, Gonzalo; Sadakane, Kunihiko
62
2014
Kernelization lower bounds through colors and IDs. Zbl 1398.68226
Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket
58
2014
Fixed-parameter algorithms for \((k, r)\)-center in planar graphs and map graphs. Zbl 1321.05256
Demaine, Erik D.; Fomin, Fedor V.; Hajiaghayi, Mohammadtaghi; Thilikos, Dimitrios M.
56
2005
Tight bounds for worst-case equilibria. Zbl 1322.91017
Czumaj, Artur; Vöcking, Berthold
50
2007
On problems as hard as CNF-SAT. Zbl 1442.68064
Cygan, Marek; Dell, Holger; Lokshtanov, Daniel; Marx, Dániel; Nederlof, Jesper; Okamoto, Yoshio; Paturi, Ramamohan; Saurabh, Saket; Wahlström, Magnus
50
2016
Combinatorial bounds via measure and conquer: bounding minimal dominating sets and applications. Zbl 1445.05101
Fomin, Fedor V.; Grandoni, Fabrizio; Pyatkin, Artem V.; Stepanov, Alexey A.
45
2008
Convergence time to Nash equilibrium in load balancing. Zbl 1192.68956
Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay
41
2007
An improved approximation for \(k\)-median and positive correlation in budgeted optimization. Zbl 1454.90069
Byrka, Jarosław; Pensyl, Thomas; Rybicki, Bartosz; Srinivasan, Aravind; Trinh, Khoa
40
2017
Finding small separators in linear time via treewidth reduction. Zbl 1301.05337
Marx, Dániel; O’Sullivan, Barry; Razgon, Igor
38
2013
Multicommodity demand flow in a tree and packing integer programs. Zbl 1192.68879
Chekuri, Chandra; Mydlarz, Marcelo; Shepherd, F. Bruce
37
2007
Approximating rank-width and clique-width quickly. Zbl 1451.05231
Oum, Sang-Il
33
2008
Additive spanners and \(({\alpha}, {\beta})\)-spanners. Zbl 1295.05094
Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth
32
2010
A better approximation ratio for the vertex cover problem. Zbl 1298.68295
Karakostas, George
32
2009
Computing almost shortest paths. Zbl 1321.05258
Elkin, Michael
31
2005
Linear kernels and single-exponential algorithms via protrusion decompositions. Zbl 1398.68245
Kim, Eun Jung; Langer, Alexander; Paul, Christophe; Reidl, Felix; Rossmanith, Peter; Sau, Ignasi; Sikdar, Somnath
31
2016
How to meet asynchronously (almost) everywhere. Zbl 1295.68171
Czyzowicz, Jurek; Pelc, Andrzej; Labourel, Arnaud
30
2012
Achieving anonymity via clustering. Zbl 1300.68023
Aggarwal, Gagan; Panigrahy, Rina; Feder, Tomás; Thomas, Dilys; Kenthapadi, Krishnaram; Khuller, Samir; Zhu, An
30
2010
Succinct ordinal trees with level-ancestor queries. Zbl 1321.68223
Geary, Richard F.; Raman, Rajeev; Raman, Venkatesh
30
2006
Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. Zbl 1333.68216
Ta-Shma, Amnon; Zwick, Uri
29
2014
Rank-maximal matchings. Zbl 1321.90116
Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E.
28
2006
Nearest-neighbor-preserving embeddings. Zbl 1192.68748
Indyk, Piotr; Naor, Assaf
28
2007
Gathering despite mischief. Zbl 1398.68054
Dieudonné, Yoann; Pelc, Andrzej; Peleg, David
28
2014
Testing planarity of partially embedded graphs. Zbl 1398.68385
Angelini, Patrizio; Di Battista, Giuseppe; Frati, Fabrizio; Jelínek, Vít; Kratochvíl, Jan; Patrignani, Maurizio; Rutter, Ignaz
28
2015
Minimizing movement. Zbl 1298.68293
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Mahini, Hamid; Sayedi-Roshkhar, Amin S.; Oveisgharan, Shayan; Zadimoghaddam, Morteza
26
2009
On a generalization of the stable roommates problem. Zbl 1321.05201
Cechlárová, Katarína; Fleiner, Tamás
26
2005
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
26
2005
Approximation algorithms for computing maximin share allocations. Zbl 1407.68540
Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin
26
2017
Length-bounded cuts and flows. Zbl 1295.68119
Baier, Georg; Erlebach, Thomas; Hall, Alexander; Köhler, Ekkehard; Kolman, Petr; Pangrác, Ondřej; Schilling, Heiko; Skutella, Martin
25
2010
Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time. Zbl 1321.68214
Baswana, Surender; Sen, Sandeep
25
2006
The relative worst order ratio for online algorithms. Zbl 1321.68512
Boyar, Joan; Favrholdt, Lene M.
25
2007
Interval deletion is fixed-parameter tractable. Zbl 1398.68220
Cao, Yixin; Marx, Dániel
25
2015
The price of anarchy in network creation games. Zbl 1295.68041
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Mahini, Hamid; Zadimoghaddam, Morteza
24
2012
A general approach to online network optimization problems. Zbl 1321.68509
Alon, Noga; Awerbuch, Baruch; Azar, Yossi; Buchbinder, Niv; Naor, Joseph (Seffi)
24
2006
Delays induce an exponential memory gap for rendezvous in trees. Zbl 1301.68203
Fraigniaud, Pierre; Pelc, Andrzej
24
2013
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
24
2014
Simultaneous PQ-ordering with applications to constrained embedding problems. Zbl 1398.68387
Bläsius, Thomas; Rutter, Ignaz
24
2016
Structure and linear-time recognition of 4-leaf powers. Zbl 1451.05040
Brandstädt, Andreas; Le, Van Bang; Sritharan, R.
24
2008
Known algorithms on graphs of bounded treewidth are probably optimal. Zbl 1454.68110
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket
24
2018
Deterministic algorithms for submodular maximization problems. Zbl 1454.68170
Buchbinder, Niv; Feldman, Moran
24
2018
Optimal constrained graph exploration. Zbl 1321.68382
Duncan, Christian A.; Kobourov, Stephen G.; Kumar, V. S. Anil
23
2006
Faster fixed parameter tractable algorithms for finding feedback vertex sets. Zbl 1321.05275
Raman, Venkatesh; Saurabh, Saket; Subramanian, C. R.
23
2006
Kernel(s) for problems with no kernel, on out-trees with many leaves. Zbl 1295.68120
Binkele-Raible, Daniel; Fernau, Henning; Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Villanger, Yngve
22
2012
Shortest paths in directed planar graphs with negative lengths: a linear-space \(O(n\log^{2} n)\)-time algorithm. Zbl 1300.05301
Klein, Philip N.; Mozes, Shay; Weimann, Oren
22
2010
Polynomial kernels for Dominating Set in graphs of bounded degeneracy and beyond. Zbl 1301.68164
Philip, Geevarghese; Raman, Venkatesh; Sikdar, Somnath
22
2012
Constraint solving via fractional edge covers. Zbl 1398.68240
Grohe, Martin; Marx, Dániel
22
2014
Optimal lower and upper bounds for representing sequences. Zbl 1398.68103
Belazzougui, Djamal; Navarro, Gonzalo
22
2015
A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. Zbl 1398.68679
Kortsarz, Guy; Nutov, Zeev
22
2016
On uniform capacitated \(k\)-median beyond the natural LP relaxation. Zbl 1451.90089
Li, Shi
22
2017
Algorithms for power savings. Zbl 1422.68018
Irani, Sandy; Shukla, Sandeep; Gupta, Rajesh
22
2007
Approximation algorithms and hardness results for cycle packing problems. Zbl 1446.68121
Krivelevich, Michael; Nutov, Zeev; Salavatipour, Mohammad R.; Verstraete, Jacques; Yuster, Raphael
22
2007
Adversarial queuing on the multiple access channel. Zbl 1295.68047
Chlebus, Bogdan S.; Kowalski, Dariusz R.; Rokicki, Mariusz A.
21
2012
Bipartite roots of graphs. Zbl 1321.05209
Lau, Lap Chi
21
2006
The string edit distance matching problem with moves. Zbl 1321.68551
Cormode, Graham; Muthukrishnan, S.
21
2007
Speed scaling with an arbitrary power function. Zbl 1301.90026
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
21
2013
Novel architectures for P2P applications: the continuous-discrete approach. Zbl 1192.68050
Naor, Moni; Wieder, Udi
21
2007
Energy-efficient algorithms for flow time minimization. Zbl 1445.68036
Albers, Susanne; Fujiwara, Hiroshi
21
2007
Tree exploration with logarithmic memory. Zbl 1295.68203
Ambühl, Christoph; Gąsieniec, Leszek; Pelc, Andrzej; Radzik, Tomasz; Zhang, Xiaohui
20
2011
Succinct indexes for strings, binary relations and multilabeled trees. Zbl 1295.68227
Barbay, Jérémy; He, Meng; Munro, J. Ian; Satti, Srinivasa Rao
20
2011
Fully compressed suffix trees. Zbl 1295.68103
Russo, Luís M. S.; Navarro, Gonzalo; Oliveira, Arlindo L.
20
2011
Low distortion spanners. Zbl 1298.05307
Pettie, Seth
20
2009
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. Zbl 1321.68558
Eppstein, David
20
2006
Compressed indexes for dynamic text collections. Zbl 1321.68261
Chan, Ho-Leung; Hon, Wing-Kai; Lam, Tak-Wah; Sadakane, Kunihiko
20
2007
Improved approximation results for the stable marriage problem. Zbl 1192.68903
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki
20
2007
Network sparsification for Steiner problems on planar and bounded-genus graphs. Zbl 1454.68114
Pilipczuk, Marcin; Pilipczuk, Michał; Sankowski, Piotr; van Leeuwen, Erik Jan
20
2018
Algorithms for capacitated rectangle stabbing and lot sizing with joint set-up costs. Zbl 1445.68347
Even, Guy; Levi, Retsef; Rawitz, Dror; Schieber, Baruch; Shahar, Shimon (Moni); Sviridenko, Maxim
20
2008
Fully dynamic algorithms for chordal graphs and split graphs. Zbl 1445.05103
Ibarra, Louis
20
2008
An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs. Zbl 1300.05294
Borradaile, Glencora; Klein, Philip; Mathieu, Claire
19
2009
Approximating minimum-cost connectivity problems via uncrossable bifamilies. Zbl 1301.68275
Nutov, Zeev
19
2012
On the set multicover problem in geometric settings. Zbl 1301.68237
Chekuri, Chandra; Clarkson, Kenneth L.; Har-Peled, Sariel
19
2012
Submodular secretary problem and extensions. Zbl 1301.91016
Bateni, Mohammadhossein; Hajiaghayi, Mohammadtaghi; Zadimoghaddam, Morteza
19
2013
Optimal branch-decomposition of planar graphs in \(O(n^3)\) time. Zbl 1445.68165
Gu, Qian-Ping; Tamaki, Hisao
19
2008
Label-guided graph exploration by a finite automaton. Zbl 1445.68157
Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David
19
2008
A 1.8 approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. Zbl 1398.68670
Even, Guy; Feldman, Jon; Kortsarz, Guy; Nutov, Zeev
19
2009
The traveling salesman problem in bounded degree graphs. Zbl 1295.90060
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko
18
2012
Improved algorithms for orienteering and related problems. Zbl 1295.05225
Chekuri, Chandra; Korula, Nitish; Pál, Martin
18
2012
Santa Claus meets hypergraph matchings. Zbl 1295.05165
Asadpour, Arash; Feige, Uriel; Saberi, Amin
18
2012
Low-dimensional lattice basis reduction revisited. Zbl 1300.11133
Nguyen, Phong Q.; Stehlé, Damien
18
2009
Clustering for metric and nonmetric distance measures. Zbl 1300.68050
Ackermann, Marcel R.; Blömer, Johannes; Sohler, Christian
18
2010
Fast sparse matrix multiplication. Zbl 1321.65073
Yuster, Raphael; Zwick, Uri
18
2005
Dynamic text and static pattern matching. Zbl 1321.68547
Amir, Amihood; Landau, Gad M.; Lewenstein, Moshe; Sokol, Dina
18
2007
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. Zbl 1454.68098
Coudert, David; Ducoffe, Guillaume; Popa, Alexandru
18
2019
Faster pseudopolynomial time algorithms for subset sum. Zbl 1454.90076
Koiliaris, Konstantinos; Xu, Chao
18
2019
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
18
2019
Deterministic conflict-free coloring for intervals: from offline to online. Zbl 1445.68357
Bar-Noy, Amotz; Cheilaris, Panagiotis; Smorodinsky, Shakhar
18
2008
Minimizing movement in mobile facility location problems. Zbl 1295.90019
Friggstad, Zachary; Salavatipour, Mohammad R.
17
2011
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error. Zbl 1301.68162
Jayram, T. S.; Woodruff, David P.
17
2013
Limits and applications of group algebras for parameterized problems. Zbl 1445.68343
Koutis, Ioannis; Williams, Ryan
17
2016
Maximizing \(k\)-submodular functions and beyond. Zbl 1445.68371
Ward, Justin; Živný, Stanislav
17
2016
Dynamic entropy-compressed sequences and full-text indexes. Zbl 1446.68043
Mäkinen, Veli; Navarro, Gonzalo
17
2008
Fault-tolerant facility location. Zbl 1445.68356
Swamy, Chaitanya; Shmoys, David B.
17
2008
Fully polynomial-time parameterized computations for graphs and matrices of low treewidth. Zbl 1457.05110
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Pilipczuk, Michał; Wrochna, Marcin
17
2018
Taxes for linear atomic congestion games. Zbl 1295.91006
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis
16
2010
Fully dynamic randomized algorithms for graph spanners. Zbl 1295.05221
Baswana, Surender; Khurana, Sumeet; Sarkar, Soumojit
16
2012
Online metric algorithms with untrusted predictions. Zbl 07753170
Antoniadis, Antonios; Coester, Christian; Eliáš, Marek; Polak, Adam; Simon, Bertrand
2
2023
Near-optimal time-energy trade-offs for deterministic leader election. Zbl 07753187
Chang, Yi-Jun; Duan, Ran; Jiang, Shunhua
2
2023
On the complexity of string matching for graphs. Zbl 07753172
Equi, Massimo; Mäkinen, Veli; Tomescu, Alexandru I.; Grossi, Roberto
1
2023
Almost-optimal deterministic treasure hunt in unweighted graphs. Zbl 07753173
Bouchard, Sébastien; Dieudonné, Yoann; Labourel, Arnaud; Pelc, Andrzej
1
2023
Polynomial-time algorithm for maximum weight independent set on \(P_6\)-free graphs. Zbl 07758397
Grzesik, Andrzej; Klimošová, Tereza; Pilipczuk, Marcin; Pilipczuk, Michał
5
2022
Solving connectivity problems parameterized by treewidth in single exponential time. Zbl 07758411
Cygan, Marek; Nederlof, Jesper; Pilipczuk, Marcin; Pilipczuk, Michał; Van Rooij, Johan M. M.; Wojtaszczyk, Jakub Onufry
3
2022
Efficient shortest paths in scale-free networks with underlying hyperbolic geometry. Zbl 07758413
Bläsius, Thomas; Freiberger, Cedric; Friedrich, Tobias; Katzmann, Maximilian; Montenegro-Retana, Felix; Thieffry, Marianne
3
2022
\(k\)-apices of minor-closed graph classes. II. Parameterized algorithms. Zbl 07758415
Sau, Ignasi; Stamoulis, Giannos; Thilikos, Dimitrios M.
3
2022
Optimal parameterized algorithms for planar facility location problems using Voronoi diagrams. Zbl 07758407
Marx, Dániel; Pilipczuk, Michał
2
2022
Hypergraph isomorphism for groups with restricted composition factors. Zbl 07758421
Neuen, Daniel
2
2022
Algorithms for weighted independent transversals and strong colouring. Zbl 07758394
Graf, Alessandra; Harris, David G.; Haxell, Penny
1
2022
A simple algorithm for optimal search trees with two-way comparisons. Zbl 07758395
Chrobak, Marek; Golin, Mordecai; Munro, J. Ian; Young, Neal E.
1
2022
SETH-based lower bounds for subset sum and bicriteria path. Zbl 07758400
Abboud, Amir; Bringmann, Karl; Hermelin, Danny; Shabtay, Dvir
1
2022
Time dependent biased random walks. Zbl 07758406
Haslegrave, John; Sauerwald, Thomas; Sylvester, John
1
2022
Computing the inverse geodesic length in planar graphs and graphs of bounded treewidth. Zbl 07758408
Cabello, Sergio
1
2022
Network design for \(s\)-\(t\) effective resistance. Zbl 07758416
Chan, Pak Hay; Lau, Lap Chi; Schild, Aaron; Wong, Sam Chiu-Wai; Zhou, Hong
1
2022
Online algorithms for weighted paging with predictions. Zbl 07758433
Jiang, Zhihao; Panigrahi, Debmalya; Sun, Kevin
1
2022
Approximating geometric knapsack via L-packings. Zbl 07479303
Gálvez, Waldo; Grandoni, Fabrizio; Ingala, Salvatore; Heydrich, Sandy; Khan, Arindam; Wiese, Andreas
7
2021
Graph sparsification for derandomizing massively parallel computation with low space. Zbl 07475095
Czumaj, Artur; Davies, Peter; Parter, Merav
4
2021
Finding a shortest odd hole. Zbl 07475092
Chudnovsky, Maria; Scott, Alex; Seymour, Paul
2
2021
Sparse backbone and optimal distributed SINR algorithms. Zbl 07475096
Halldórsson, Magnús M.; Tonoyan, Tigran
2
2021
The quest for strong inapproximability results with perfect completeness. Zbl 07475107
Brakensiek, Joshua; Guruswami, Venkatesan
2
2021
2-approximating feedback vertex set in tournaments. Zbl 07475090
Lokshtanov, Daniel; Misra, Pranabendu; Mukherjee, Joydeep; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket
1
2021
Parameterized approximation algorithms for bidirected Steiner network problems. Zbl 07475091
Chitnis, Rajesh; Feldmann, Andreas Emil; Manurangsi, Pasin
1
2021
Navigating in trees with permanently noisy advice. Zbl 07475094
Boczkowski, Lucas; Feige, Uriel; Korman, Amos; Rodeh, Yoav
1
2021
Memory-adjustable navigation piles with applications to sorting and convex hulls. Zbl 07475097
Darwish, Omar; Elmasry, Amr; Katajainen, Jyrki
1
2021
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. Zbl 07475101
Viola, Caterina; Živný, Stanislav
1
2021
Zip trees. Zbl 07479304
Tarjan, Robert E.; Levy, Caleb; Timmel, Stephen
1
2021
Proximity results and faster algorithms for integer programming using the Steinitz lemma. Zbl 1454.90029
Eisenbrand, Friedrich; Weismantel, Robert
16
2020
Optimal-time dictionary-compressed indexes. Zbl 07471493
Christiansen, Anders Roy; Ettienne, Mikko Berggren; Kociumaka, Tomasz; Navarro, Gonzalo; Prezza, Nicola
11
2020
Linear-time string indexing and analysis in small space. Zbl 1485.68079
Belazzougui, Djamal; Cunial, Fabio; Kärkkäinen, Juha; Mäkinen, Veli
8
2020
A linear-time algorithm for seeds computation. Zbl 1484.68347
Kociumaka, Tomasz; Kubica, Marcin; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz
7
2020
More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. Zbl 1454.68210
Chan, Timothy M.
6
2020
Symmetry exploitation for online machine covering with bounded migration. Zbl 07678775
Gálvez, Waldo; Soto, José A.; Verschae, José
5
2020
Doubly balanced connected graph partitioning. Zbl 1484.05169
Soltan, Saleh; Yannakakis, Mihalis; Zussman, Gil
5
2020
Holant clones and the approximability of conservative holant problems. Zbl 1484.68144
Backens, Miriam; Goldberg, Leslie Ann
5
2020
Enumerating minimal dominating sets in \(K_t\)-free graphs and variants. Zbl 1484.68153
Bonamy, Marthe; Defrain, Oscar; Heinrich, Marc; Pilipczuk, Michał; Raymond, Jean-Florent
5
2020
Tight bounds for online TSP on the line. Zbl 07471488
Bjelde, Antje; Hackfeld, Jan; Disser, Yann; Hansknecht, Christoph; Lipmann, Maarten; Meißner, Julie; Schlöter, Miriam; Schewior, Kevin; Stougie, Leen
5
2020
The non-uniform \(k\)-center problem. Zbl 1524.68440
Chakrabarty, Deeparnab; Goyal, Prachi; Krishnaswamy, Ravishankar
4
2020
Faster replacement paths and distance sensitivity oracles. Zbl 1484.68056
Grandoni, Fabrizio; Vassilevska Williams, Virginia
4
2020
Distributed edge coloring and a special case of the constructive Lovász local lemma. Zbl 1454.68167
Chang, Yi-Jun; He, Qizheng; Li, Wenzheng; Pettie, Seth; Uitto, Jara
4
2020
Solving the sigma-tau problem. Zbl 1458.05108
Sawada, Joe; Williams, Aaron
4
2020
Approximation schemes for low-rank binary matrix approximation problems. Zbl 1454.68180
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket
4
2020
The complexity of cake cutting with unequal shares. Zbl 1486.91040
Cseh, Ágnes; Fleiner, Tamás
4
2020
An improved isomorphism test for bounded-tree-width graphs. Zbl 1484.68161
Grohe, Martin; Neuen, Daniel; Schweitzer, Pascal; Wiebking, Daniel
4
2020
Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. Zbl 07471487
Chan, Timothy M.; Williams, R. Ryan
4
2020
Randomized contractions meet lean decompositions. Zbl 07471491
Cygan, Marek; Komosa, Paweł; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket; Wahlström, Magnus
4
2020
Parameterized hardness of art gallery problems. Zbl 07678774
Bonnet, Édouard; Miltzow, Tillmann
3
2020
Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems. Zbl 07678783
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav
3
2020
Randomized memoryless algorithms for the weighted and the generalized \(k\)-server problems. Zbl 1484.68340
Chiplunkar, Ashish; Vishwanathan, Sundar
3
2020
Time- and space-optimal algorithm for the many-visits TSP. Zbl 1483.68508
Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
3
2020
Maximum matching in the online batch-arrival model. Zbl 07678781
Lee, Euiwoong; Singla, Sahil
2
2020
Deterministic sparse suffix sorting in the restore model. Zbl 07678782
Fischer, Johannes; I, Tomohiro; Köppl, Dominik
2
2020
Edge estimation with independent set oracles. Zbl 07678784
Beame, Paul; Har-Peled, Sariel; Ramamoorthy, Sivaramakrishnan Natarajan; Rashtchian, Cyrus; Sinha, Makrand
2
2020
Scheduling when you do not know the number of machines. Zbl 1454.90021
Stein, Clifford; Zhong, Mingxian
2
2020
Algorithms to approximate column-sparse packing problems. Zbl 1454.68176
Brubach, Brian; Sankararaman, Karthik A.; Srinivasan, Aravind; Xu, Pan
2
2020
Lower bounds for the parameterized complexity of minimum fill-in and other completion problems. Zbl 1484.68152
Bliznets, Ivan; Cygan, Marek; Komosa, Paweł; Pilipczuk, Michał; Mach, Lukáš
2
2020
Nearly ETH-tight algorithms for planar Steiner tree with terminals on few faces. Zbl 1484.68166
Kisfaludi-Bak, Sándor; Nederlof, Jesper; van Leeuwen, Erik Jan
2
2020
Random walks on small world networks. Zbl 1484.05195
Dyer, Martin E.; Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark; Vigoda, Eric
2
2020
Fine-grained complexity analysis of two classic TSP variants. Zbl 07471490
de Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard
2
2020
Dynamic parameterized problems and algorithms. Zbl 07678777
Alman, Josh; Mnich, Matthias; Williams, Virginia Vassilevska
1
2020
Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). Zbl 1527.68045
Bringmann, Karl; Gawrychowski, Paweł; Mozes, Shay; Weimann, Oren
1
2020
Point-width and max-CSPs. Zbl 07678786
Carbonnel, Clément; Romero, Miguel; Živný, Stanislav
1
2020
Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search. Zbl 1484.68055
Gawrychowski, Paweł; Mozes, Shay; Weimann, Oren
1
2020
Testing bounded arboricity. Zbl 1484.68158
Eden, Talya; Levi, Reut; Ron, Dana
1
2020
Ramsey spanning trees and their applications. Zbl 1484.68147
Abraham, Ittai; Chechik, Shiri; Elkin, Michael; Filtser, Arnold; Neiman, Ofer
1
2020
A unified PTAS for prize collecting TSP and Steiner tree problem in doubling metrics. Zbl 1484.68331
Chan, T.-H. Hubert; Jiang, Haotian; Jiang, Shaofeng H.-C.
1
2020
Periods of iterations of functions with restricted preimage sizes. Zbl 1491.60017
Martins, Rodrigo S. V.; Panario, Daniel; Qureshi, Claudio; Schmutz, Eric
1
2020
Approximating spanners and directed Steiner forest. Upper and lower bounds. Zbl 1484.68156
Chlamtáč, Eden; Dinitz, Michael; Kortsarz, Guy; Laekhanukit, Bundit
1
2020
A PTAS for Euclidean TSP with hyperplane neighborhoods. Zbl 1484.68269
Antoniadis, Antonios; Fleszar, Krzysztof; Hoeksma, Ruben; Schewior, Kevin
1
2020
Improved dynamic graph coloring. Zbl 1484.68172
Solomon, Shay; Wein, Nicole
1
2020
Oblivious resampling oracles and parallel algorithms for the lopsided Lovász local lemma. Zbl 07471486
Harris, David G.
1
2020
Zeros of Holant problems: locations and algorithms. Zbl 07471489
Guo, Heng; Liao, Chao; Lu, Pinyan; Zhang, Chihao
1
2020
Journey to the center of the point set. Zbl 07471494
Har-Peled, Sariel; Jones, Mitchell
1
2020
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. Zbl 1454.68098
Coudert, David; Ducoffe, Guillaume; Popa, Alexandru
18
2019
Faster pseudopolynomial time algorithms for subset sum. Zbl 1454.90076
Koiliaris, Konstantinos; Xu, Chao
18
2019
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
18
2019
The complexity of independent set reconfiguration on bipartite graphs. Zbl 1454.68111
Lokshtanov, Daniel; Mouawad, Amer E.
16
2019
Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. Zbl 1443.68122
Cabello, Sergio
16
2019
A lottery model for center-type problems with outliers. Zbl 1454.68182
Harris, David G.; Pensyl, Thomas; Srinivasan, Aravind; Trinh, Khoa
12
2019
Feedback vertex set inspired kernel for chordal vertex deletion. Zbl 1454.68088
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav
12
2019
Clique-width. III: Hamiltonian cycle and the odd case of graph coloring. Zbl 1458.05245
Fomin, Fedor V.; Golovach, Petr A.; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
11
2019
Domination when the stars are out. Zbl 1454.68104
Hermelin, Danny; Mnich, Matthias; Van Leeuwen, Erik Jan; Woeginger, Gerhard
10
2019
Beating approximation factor two for weighted tree augmentation with bounded costs. Zbl 1454.68085
Adjiashvili, David
9
2019
Efficient algorithms for constructing very sparse spanners and emulators. Zbl 1435.68378
Elkin, Michael; Neiman, Ofer
8
2019
Subquadratic kernels for implicit 3-{Hitting Set} and 3-{Set Packing} problems. Zbl 1454.68101
Fomin, Fedor V.; Le, Tien-Nam; Lokshtanov, Daniel; Saurabh, Saket; Thomassé, Stéphan; Zehavi, Meirav
8
2019
Deterministic graph exploration with advice. Zbl 1454.68102
Gorain, Barun; Pelc, Andrzej
7
2019
Approximation schemes for clustering with outliers. Zbl 1454.68181
Friggstad, Zachary; Khodamoradi, Kamyar; Rezapour, Mohsen; Salavatipour, Mohammad R.
6
2019
Online submodular maximization with preemption. Zbl 1453.68216
Buchbinder, Niv; Feldman, Moran; Schwartz, Roy
6
2019
Exponential separations in the energy complexity of leader election. Zbl 1454.68015
Chang, Yi-Jun; Kopelowitz, Tsvi; Pettie, Seth; Wang, Ruosong; Zhan, Wei
6
2019
Completeness for first-order properties on sparse structures with algorithmic applications. Zbl 1454.68054
Gao, Jiawei; Impagliazzo, Russell; Kolokolova, Antonina; Williams, Ryan
6
2019
Online vertex-weighted bipartite matching. Beating \(1-\frac{1}{e}\) with random arrivals. Zbl 1455.68278
Huang, Zhiyi; Tang, Zhihao Gavin; Wu, Xiaowei; Zhang, Yuhao
5
2019
Generalized center problems with outliers. Zbl 1454.68177
Chakrabarty, Deeparnab; Negahbani, Maryam
5
2019
Recognizing weak embeddings of graphs. Zbl 1454.68089
Akitaya, Hugo A.; Fulek, Radoslav; Tóth, Csaba D.
5
2019
Ordered level planarity and its relationship to geodesic planarity, bi-monotonicity, and variations of level planarity. Zbl 1454.68108
Klemz, Boris; Rote, Günter
5
2019
A 4/3-approximation algorithm for the minimum 2-edge connected subgraph problem. Zbl 1454.68184
Hunkenschröder, Christoph; Vempala, Santosh; Vetta, Adrian
5
2019
Sparse dynamic programming on DAGs with small width. Zbl 1454.68112
Mäkinen, Veli; Tomescu, Alexandru I.; Kuosmanen, Anna; Paavilainen, Topi; Gagie, Travis; Chikhi, Rayan
4
2019
Approximation schemes for machine scheduling with resource (in-)dependent processing times. Zbl 1454.68185
Jansen, Klaus; Maack, Marten; Rau, Malin
4
2019
Distributed dominating set approximations beyond planar graphs. Zbl 1454.68090
Amiri, Saeed Akhoondian; Schmid, Stefan; Siebertz, Sebastian
4
2019
An optimal \(O(nm)\) algorithm for enumerating all walks common to all closed edge-covering walks of a graph. Zbl 1454.92021
Cairo, Massimo; Medvedev, Paul; Acosta, Nidia Obscura; Rizzi, Romeo; Tomescu, Alexandru I.
4
2019
...and 582 more Documents
all top 5

Cited by 5,685 Authors

104 Saurabh, Saket
64 Navarro, Gonzalo
61 Fomin, Fedor V.
55 Golovach, Petr A.
45 Lokshtanov, Daniel
39 Raman, Venkatesh
38 Pelc, Andrzej
36 Zehavi, Meirav
35 Niedermeier, Rolf
33 Munro, J. Ian
31 Pilipczuk, Marcin L.
30 Paulusma, Daniël
30 Thilikos, Dimitrios M.
29 Thankachan, Sharma V.
28 Gawrychowski, Paweł
27 Gagie, Travis
27 Jansen, Bart M. P.
25 Kratsch, Dieter
25 Marx, Dániel
25 Panolan, Fahad
24 Chan, Timothy Moon-Yew
24 Epstein, Leah
23 Nutov, Zeev
23 Ramanujan, M. S.
23 Rutter, Ignaz
22 He, Meng
22 Komusiewicz, Christian
22 Pilipczuk, Michał
22 Sadakane, Kunihiko
21 Agrawal, Akanksha
21 Halldórsson, Magnús Mar
21 Satti, Srinivasa Rao
21 Tóth, Csaba D.
20 Kratsch, Stefan
20 Nekrich, Yakov
19 Da Lozzo, Giordano
19 Sau, Ignasi
18 Bilò, Davide
18 Dieudonné, Yoann
18 Heggernes, Pinar
18 Lampis, Michael
18 Leucci, Stefano
17 Kavitha, Telikepalli
17 Majumdar, Diptapriyo
17 Misra, Pranabendu
17 Nagarajan, Viswanath
17 Nichterlein, André
17 Otachi, Yota
17 Wahlström, Magnus
16 Angelini, Patrizio
16 Gutin, Gregory Z.
16 Hajiaghayi, Mohammad Taghi
16 Jansen, Klaus
16 Shah, Rahul
16 Xu, Dachuan
15 Bandyapadhyay, Sayan
15 Czyzowicz, Jurek
15 Ducoffe, Guillaume
15 Gørtz, Inge Li
15 Grandoni, Fabrizio
15 Hon, Wing-Kai
15 Kobourov, Stephen G.
15 Kowalski, Dariusz R.
15 Levin, Asaf
15 Proietti, Guido
14 Bille, Philip
14 Bilò, Vittorio
14 Eiben, Eduard
14 Fotakis, Dimitris A.
14 Gualà, Luciano
14 Kärkkäinen, Juha
14 Kawarabayashi, Ken-ichi
14 Manzini, Giovanni
14 Mouawad, Amer E.
14 Shachnai, Hadas
14 Tamir, Tami
14 Weimann, Oren
13 Bampis, Evripidis
13 Buchin, Kevin
13 Cygan, Marek
13 Feldman, Moran
13 Gaspers, Serge
13 Jo, Seungbum
13 Larsen, Kim Skak
13 Liotta, Giuseppe
13 Moseley, Benjamin
13 Peleg, David
13 Pettie, Seth
13 Puglisi, Simon J.
13 Radoszewski, Jakub
13 Sharma, Roohani
13 Tale, Prafullkumar
13 Xiao, Mingyu
12 Baswana, Surender
12 Boyar, Joan F.
12 Eppstein, David Arthur
12 Fernau, Henning
12 Grossi, Roberto
12 Hermelin, Danny
12 Kobayashi, Yusuke
...and 5,585 more Authors
all top 5

Cited in 301 Journals

492 Theoretical Computer Science
463 Algorithmica
151 Discrete Applied Mathematics
139 SIAM Journal on Computing
119 Journal of Computer and System Sciences
118 Theory of Computing Systems
100 Journal of Combinatorial Optimization
94 Information Processing Letters
92 SIAM Journal on Discrete Mathematics
65 Distributed Computing
60 Computational Geometry
55 Journal of Discrete Algorithms
53 Information and Computation
53 Mathematical Programming. Series A. Series B
52 Discrete & Computational Geometry
37 European Journal of Operational Research
32 Mathematics of Operations Research
31 Journal of Scheduling
31 Discrete Optimization
30 ACM Transactions on Algorithms
27 Random Structures & Algorithms
27 ACM Journal of Experimental Algorithmics
26 Operations Research Letters
26 Journal of Graph Algorithms and Applications
26 Algorithms
25 Discrete Mathematics
24 Computers & Operations Research
23 Artificial Intelligence
21 Journal of Combinatorial Theory. Series B
20 Annals of Operations Research
20 The Electronic Journal of Combinatorics
19 Networks
19 Discrete Mathematics, Algorithms and Applications
18 International Journal of Foundations of Computer Science
17 Information Sciences
16 Journal of Global Optimization
15 Operations Research
15 Journal of Machine Learning Research (JMLR)
14 European Journal of Combinatorics
14 Graphs and Combinatorics
14 Optimization Letters
12 Games and Economic Behavior
12 SIAM Journal on Optimization
12 Computer Science Review
11 Journal of Graph Theory
11 International Journal of Computational Geometry & Applications
11 INFORMS Journal on Computing
10 Acta Informatica
10 Combinatorics, Probability and Computing
10 Journal of the ACM
9 Linear Algebra and its Applications
9 Data Mining and Knowledge Discovery
8 Journal of Symbolic Computation
8 The Journal of Artificial Intelligence Research (JAIR)
8 International Transactions in Operational Research
8 Constraints
8 Mathematics in Computer Science
7 Computing
7 Designs, Codes and Cryptography
6 Journal of Cryptology
6 Logical Methods in Computer Science
5 Journal of Mathematical Economics
5 Advances in Applied Mathematics
5 Mathematical Social Sciences
5 Social Choice and Welfare
5 Asia-Pacific Journal of Operational Research
5 Journal of Parallel and Distributed Computing
5 Machine Learning
5 Computational Complexity
5 Computational Optimization and Applications
5 SIAM Journal on Scientific Computing
5 Mathematical Methods of Operations Research
5 Foundations of Computational Mathematics
5 Journal of the Operations Research Society of China
5 Electronic Journal of Graph Theory and Applications
4 Journal of Computational Physics
4 Mathematics of Computation
4 Applied Mathematics and Computation
4 Journal of Combinatorial Theory. Series A
4 Combinatorica
4 International Journal of Computer Mathematics
4 Cybernetics and Systems Analysis
4 Annals of Mathematics and Artificial Intelligence
4 International Journal of Applied Mathematics and Computer Science
4 RAIRO. Operations Research
4 Internet Mathematics
4 SN Operations Research Forum
3 Journal of Mathematical Biology
3 Physica A
3 ACM Transactions on Database Systems
3 International Journal of Game Theory
3 Journal of Economic Theory
3 Naval Research Logistics
3 Probability Theory and Related Fields
3 Journal of Complexity
3 MSCS. Mathematical Structures in Computer Science
3 Computational Mathematics and Mathematical Physics
3 SIAM Review
3 Top
3 Electronic Journal of Probability
...and 201 more Journals
all top 5

Cited in 48 Fields

3,325 Computer science (68-XX)
1,433 Combinatorics (05-XX)
1,040 Operations research, mathematical programming (90-XX)
366 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
101 Numerical analysis (65-XX)
97 Statistics (62-XX)
82 Information and communication theory, circuits (94-XX)
72 Probability theory and stochastic processes (60-XX)
68 Biology and other natural sciences (92-XX)
64 Convex and discrete geometry (52-XX)
44 Number theory (11-XX)
31 Linear and multilinear algebra; matrix theory (15-XX)
22 Mathematical logic and foundations (03-XX)
22 Functional analysis (46-XX)
20 Order, lattices, ordered algebraic structures (06-XX)
18 Systems theory; control (93-XX)
14 Quantum theory (81-XX)
13 Calculus of variations and optimal control; optimization (49-XX)
11 Algebraic topology (55-XX)
11 Manifolds and cell complexes (57-XX)
11 Statistical mechanics, structure of matter (82-XX)
10 Dynamical systems and ergodic theory (37-XX)
9 Group theory and generalizations (20-XX)
8 Geometry (51-XX)
8 General topology (54-XX)
7 Commutative algebra (13-XX)
5 General algebraic systems (08-XX)
5 Functions of a complex variable (30-XX)
5 Approximations and expansions (41-XX)
5 Fluid mechanics (76-XX)
4 Algebraic geometry (14-XX)
3 General and overarching topics; collections (00-XX)
3 History and biography (01-XX)
3 Measure and integration (28-XX)
3 Differential geometry (53-XX)
2 Category theory; homological algebra (18-XX)
2 Real functions (26-XX)
2 Partial differential equations (35-XX)
2 Difference and functional equations (39-XX)
1 Field theory and polynomials (12-XX)
1 Associative rings and algebras (16-XX)
1 Special functions (33-XX)
1 Ordinary differential equations (34-XX)
1 Sequences, series, summability (40-XX)
1 Harmonic analysis on Euclidean spaces (42-XX)
1 Global analysis, analysis on manifolds (58-XX)
1 Mechanics of deformable solids (74-XX)
1 Relativity and gravitational theory (83-XX)

Citations by Year