×

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,341 more Authors

Publications by Year

Citations contained in zbMATH Open

695 Publications have been cited 6,336 times in 4,724 Documents Cited by Year
Compressed representations of sequences and full-text indexes. Zbl 1321.68263
Ferragina, Paolo; Manzini, Giovanni; Mäkinen, Veli; Navarro, Gonzalo
184
2007
A \(4k^2\) kernel for feedback vertex set. Zbl 1300.05236
Thomassé, Stéphan
89
2010
Succinct indexable dictionaries with applications to encoding \(k\)-ary trees, prefix sums and multisets. Zbl 1446.68046
Raman, Rajeev; Raman, Venkatesh; Satti, Srinivasa Rao
85
2007
Algorithmic construction of sets for \(k\)-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
78
2006
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
69
2012
Faster parameterized algorithms using linear programming. Zbl 1398.68254
Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket
69
2014
Fully functional static and dynamic succinct trees. Zbl 1333.68084
Navarro, Gonzalo; Sadakane, Kunihiko
66
2014
Kernelization lower bounds through colors and IDs. Zbl 1398.68226
Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket
61
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.
60
2005
Tight bounds for worst-case equilibria. Zbl 1322.91017
Czumaj, Artur; Vöcking, Berthold
52
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
51
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.
47
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
39
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
35
2008
Additive spanners and \(({\alpha}, {\beta})\)-spanners. Zbl 1295.05094
Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth
34
2010
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
33
2016
Computing almost shortest paths. Zbl 1321.05258
Elkin, Michael
32
2005
Succinct ordinal trees with level-ancestor queries. Zbl 1321.68223
Geary, Richard F.; Raman, Rajeev; Raman, Venkatesh
32
2006
A better approximation ratio for the vertex cover problem. Zbl 1298.68295
Karakostas, George
32
2009
Achieving anonymity via clustering. Zbl 1300.68023
Aggarwal, Gagan; Panigrahy, Rina; Feder, Tomás; Thomas, Dilys; Kenthapadi, Krishnaram; Khuller, Samir; Zhu, An
31
2010
Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. Zbl 1333.68216
Ta-Shma, Amnon; Zwick, Uri
30
2014
How to meet asynchronously (almost) everywhere. Zbl 1295.68171
Czyzowicz, Jurek; Pelc, Andrzej; Labourel, Arnaud
30
2012
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
29
2015
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
28
2005
Minimizing movement. Zbl 1298.68293
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Mahini, Hamid; Sayedi-Roshkhar, Amin S.; Oveisgharan, Shayan; Zadimoghaddam, Morteza
28
2009
Rank-maximal matchings. Zbl 1321.90116
Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E.
28
2006
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
28
2010
Interval deletion is fixed-parameter tractable. Zbl 1398.68220
Cao, Yixin; Marx, Dániel
28
2015
Optimal branch-decomposition of planar graphs in \(O(n^3)\) time. Zbl 1445.68165
Gu, Qian-Ping; Tamaki, Hisao
28
2008
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
On a generalization of the stable roommates problem. Zbl 1321.05201
Cechlárová, Katarína; Fleiner, Tamás
26
2005
Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time. Zbl 1321.68214
Baswana, Surender; Sen, Sandeep
26
2006
The price of anarchy in network creation games. Zbl 1295.68041
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Mahini, Hamid; Zadimoghaddam, Morteza
26
2012
Approximation algorithms for computing maximin share allocations. Zbl 1407.68540
Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin
26
2017
Faster fixed parameter tractable algorithms for finding feedback vertex sets. Zbl 1321.05275
Raman, Venkatesh; Saurabh, Saket; Subramanian, C. R.
25
2006
The relative worst order ratio for online algorithms. Zbl 1321.68512
Boyar, Joan; Favrholdt, Lene M.
25
2007
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
25
2014
Known algorithms on graphs of bounded treewidth are probably optimal. Zbl 1454.68110
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket
25
2018
Simultaneous PQ-ordering with applications to constrained embedding problems. Zbl 1398.68387
Bläsius, Thomas; Rutter, Ignaz
25
2016
Approximation algorithms and hardness results for cycle packing problems. Zbl 1446.68121
Krivelevich, Michael; Nutov, Zeev; Salavatipour, Mohammad R.; Verstraete, Jacques; Yuster, Raphael
25
2007
Structure and linear-time recognition of 4-leaf powers. Zbl 1451.05040
Brandstädt, Andreas; Le, Van Bang; Sritharan, R.
25
2008
Delays induce an exponential memory gap for rendezvous in trees. Zbl 1301.68203
Fraigniaud, Pierre; Pelc, Andrzej
24
2013
A general approach to online network optimization problems. Zbl 1321.68509
Alon, Noga; Awerbuch, Baruch; Azar, Yossi; Buchbinder, Niv; Naor, Joseph (Seffi)
24
2006
Optimal lower and upper bounds for representing sequences. Zbl 1398.68103
Belazzougui, Djamal; Navarro, Gonzalo
24
2015
Algorithms for power savings. Zbl 1422.68018
Irani, Sandy; Shukla, Sandeep; Gupta, Rajesh
24
2007
A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. Zbl 1398.68679
Kortsarz, Guy; Nutov, Zeev
24
2016
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
Polynomial kernels for Dominating Set in graphs of bounded degeneracy and beyond. Zbl 1301.68164
Philip, Geevarghese; Raman, Venkatesh; Sikdar, Somnath
23
2012
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
23
2012
Constraint solving via fractional edge covers. Zbl 1398.68240
Grohe, Martin; Marx, Dániel
23
2014
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
Low distortion spanners. Zbl 1298.05307
Pettie, Seth
22
2009
The string edit distance matching problem with moves. Zbl 1321.68551
Cormode, Graham; Muthukrishnan, S.
22
2007
Improved approximation results for the stable marriage problem. Zbl 1192.68903
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki, Shuichi; Yanagisawa, Hiroki
22
2007
On uniform capacitated \(k\)-median beyond the natural LP relaxation. Zbl 1451.90089
Li, Shi
22
2017
Energy-efficient algorithms for flow time minimization. Zbl 1445.68036
Albers, Susanne; Fujiwara, Hiroshi
22
2007
Bipartite roots of graphs. Zbl 1321.05209
Lau, Lap Chi
21
2006
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. Zbl 1321.68558
Eppstein, David
21
2006
Speed scaling with an arbitrary power function. Zbl 1301.90026
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
21
2013
Adversarial queuing on the multiple access channel. Zbl 1295.68047
Chlebus, Bogdan S.; Kowalski, Dariusz R.; Rokicki, Mariusz A.
21
2012
Improved algorithms for orienteering and related problems. Zbl 1295.05225
Chekuri, Chandra; Korula, Nitish; Pál, Martin
21
2012
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
21
2008
Deterministic conflict-free coloring for intervals: from offline to online. Zbl 1445.68357
Bar-Noy, Amotz; Cheilaris, Panagiotis; Smorodinsky, Shakhar
21
2008
Novel architectures for P2P applications: the continuous-discrete approach. Zbl 1192.68050
Naor, Moni; Wieder, Udi
21
2007
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. Zbl 1454.68098
Coudert, David; Ducoffe, Guillaume; Popa, Alexandru
21
2019
Compressed indexes for dynamic text collections. Zbl 1321.68261
Chan, Ho-Leung; Hon, Wing-Kai; Lam, Tak-Wah; Sadakane, Kunihiko
20
2007
On the set multicover problem in geometric settings. Zbl 1301.68237
Chekuri, Chandra; Clarkson, Kenneth L.; Har-Peled, Sariel
20
2012
An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs. Zbl 1300.05294
Borradaile, Glencora; Klein, Philip; Mathieu, Claire
20
2009
Clustering for metric and nonmetric distance measures. Zbl 1300.68050
Ackermann, Marcel R.; Blömer, Johannes; Sohler, Christian
20
2010
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
Tree exploration with logarithmic memory. Zbl 1295.68203
Ambühl, Christoph; Gąsieniec, Leszek; Pelc, Andrzej; Radzik, Tomasz; Zhang, Xiaohui
20
2011
Fully dynamic algorithms for chordal graphs and split graphs. Zbl 1445.05103
Ibarra, Louis
20
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
20
2009
Faster pseudopolynomial time algorithms for subset sum. Zbl 1454.90076
Koiliaris, Konstantinos; Xu, Chao
20
2019
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
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
20
2019
Dynamic text and static pattern matching. Zbl 1321.68547
Amir, Amihood; Landau, Gad M.; Lewenstein, Moshe; Sokol, Dina
19
2007
Approximating minimum-cost connectivity problems via uncrossable bifamilies. Zbl 1301.68275
Nutov, Zeev
19
2012
Submodular secretary problem and extensions. Zbl 1301.91016
Bateni, Mohammadhossein; Hajiaghayi, Mohammadtaghi; Zadimoghaddam, Morteza
19
2013
The traveling salesman problem in bounded degree graphs. Zbl 1295.90060
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko
19
2012
Santa Claus meets hypergraph matchings. Zbl 1295.05165
Asadpour, Arash; Feige, Uriel; Saberi, Amin
19
2012
Label-guided graph exploration by a finite automaton. Zbl 1445.68157
Cohen, Reuven; Fraigniaud, Pierre; Ilcinkas, David; Korman, Amos; Peleg, David
19
2008
Fast sparse matrix multiplication. Zbl 1321.65073
Yuster, Raphael; Zwick, Uri
18
2005
A linear-time approximation algorithm for weighted matchings in graphs. Zbl 1321.05279
Vinkemeier, Doratha E. Drake; Hougardy, Stefan
18
2005
Comparison-based time-space lower bounds for selection. Zbl 1300.68032
Chan, Timothy M.
18
2010
Low-dimensional lattice basis reduction revisited. Zbl 1300.11133
Nguyen, Phong Q.; Stehlé, Damien
18
2009
An optimal decomposition algorithm for tree edit distance. Zbl 1300.68057
Demaine, Erik D.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren
18
2009
Fully dynamic randomized algorithms for graph spanners. Zbl 1295.05221
Baswana, Surender; Khurana, Sumeet; Sarkar, Soumojit
18
2012
Directed subset feedback vertex set is fixed-parameter tractable. Zbl 1398.68222
Chitnis, Rajesh; Cygan, Marek; Hajiaghayi, Mohammataghi; Marx, Dániel
18
2015
Limits and applications of group algebras for parameterized problems. Zbl 1445.68343
Koutis, Ioannis; Williams, Ryan
18
2016
Fault-tolerant facility location. Zbl 1445.68356
Swamy, Chaitanya; Shmoys, David B.
18
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
18
2018
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error. Zbl 1301.68162
Jayram, T. S.; Woodruff, David P.
17
2013
Monotone edge flips to an orientation of maximum edge-connectivity à la Nash-Williams. Zbl 07753157
Ito, Takehiro; Iwamasa, Yuni; Kakimura, Naonori; Kamiyama, Naoyuki; Kobayashi, Yusuke; Maezawa, Shun-Ichi; Nozaki, Yuta; Okamoto, Yoshio; Ozeki, Kenta
2
2023
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
Counting homomorphic cycles in degenerate graphs. Zbl 07753153
Gishboliner, Lior; Levanzov, Yevgeny; Shapira, Asaf; Yuster, Raphael
1
2023
A linear-time \(n^{0.4}\)-approximation for longest common subsequence. Zbl 07753160
Bringmann, Karl; Cohen-Addad, Vincent; Das, Debarati
1
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ł
7
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
4
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
Algorithms for weighted independent transversals and strong colouring. Zbl 07758394
Graf, Alessandra; Harris, David G.; Haxell, Penny
2
2022
SETH-based lower bounds for subset sum and bicriteria path. Zbl 07758400
Abboud, Amir; Bringmann, Karl; Hermelin, Danny; Shabtay, Dvir
2
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
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
Fully dynamic \((\Delta +1)\)-coloring in \(O(1)\) update time. Zbl 07758404
Bhattacharya, Sayan; Grandoni, Fabrizio; Kulkarni, Janardhan; Liu, Quanquan C.; Solomon, Shay
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
Detecting feedback vertex sets of size \(k\) in \(O^\star (2.7^k)\) time. Zbl 07758428
Li, Jason; Nederlof, Jesper
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
5
2021
Finding a shortest odd hole. Zbl 07475092
Chudnovsky, Maria; Scott, Alex; Seymour, Paul
3
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
A deamortization approach for dynamic spanner and dynamic maximal matching. Zbl 07479299
Bernstein, Aaron; Forster, Sebastian; Henzinger, Monika
1
2021
Querying a matrix through matrix-vector products. Zbl 07479301
Sun, Xiaoming; Woodruff, David P.; Yang, Guang; Zhang, Jialin
1
2021
Zip trees. Zbl 07479304
Tarjan, Robert E.; Levy, Caleb; Timmel, Stephen
1
2021
Better distance preservers and additive spanners. Zbl 07479306
Bodwin, Greg; Williams, Virginia Vassilevska
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
Improving the smoothed complexity of FLIP for max cut problems. Zbl 07475098
Bibak, Ali; Carlson, Charles; Chandrasekaran, Karthekeyan
1
2021
The combined basic LP and affine IP relaxation for promise VCSPs on infinite domains. Zbl 07475101
Viola, Caterina; Živný, Stanislav
1
2021
Approximate counting of \(k\)-paths: simpler, deterministic, and in polynomial space. Zbl 07475106
Björklund, Andreas; Lokshtanov, Daniel; Saurabh, Saket; Zehavi, Meirav
1
2021
2-approximating feedback vertex set in tournaments. Zbl 07475090
Lokshtanov, Daniel; Misra, Pranabendu; Mukherjee, Joydeep; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket
1
2021
Proximity results and faster algorithms for integer programming using the Steinitz lemma. Zbl 1454.90029
Eisenbrand, Friedrich; Weismantel, Robert
17
2020
Optimal-time dictionary-compressed indexes. Zbl 07471493
Christiansen, Anders Roy; Ettienne, Mikko Berggren; Kociumaka, Tomasz; Navarro, Gonzalo; Prezza, Nicola
14
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
8
2020
More logarithmic-factor speedups for 3SUM, (median,+)-convolution, and some geometric 3SUM-hard problems. Zbl 1454.68210
Chan, Timothy M.
7
2020
Doubly balanced connected graph partitioning. Zbl 1484.05169
Soltan, Saleh; Yannakakis, Mihalis; Zussman, Gil
6
2020
Faster replacement paths and distance sensitivity oracles. Zbl 1484.68056
Grandoni, Fabrizio; Vassilevska Williams, Virginia
6
2020
The non-uniform \(k\)-center problem. Zbl 1524.68440
Chakrabarty, Deeparnab; Goyal, Prachi; Krishnaswamy, Ravishankar
6
2020
Deterministic APSP, orthogonal vectors, and more: quickly derandomizing Razborov-Smolensky. Zbl 07471487
Chan, Timothy M.; Williams, R. Ryan
6
2020
Holant clones and the approximability of conservative holant problems. Zbl 1484.68144
Backens, Miriam; Goldberg, Leslie Ann
5
2020
An improved isomorphism test for bounded-tree-width graphs. Zbl 1484.68161
Grohe, Martin; Neuen, Daniel; Schweitzer, Pascal; Wiebking, Daniel
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
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
5
2020
Solving the sigma-tau problem. Zbl 1458.05108
Sawada, Joe; Williams, Aaron
5
2020
Symmetry exploitation for online machine covering with bounded migration. Zbl 07678775
Gálvez, Waldo; Soto, José A.; Verschae, José
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 complexity of cake cutting with unequal shares. Zbl 1486.91040
Cseh, Ágnes; Fleiner, Tamás
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
Parameterized hardness of art gallery problems. Zbl 07678774
Bonnet, Édouard; Miltzow, Tillmann
4
2020
Polylogarithmic approximation algorithms for weighted-\(\mathcal{F}\)-deletion problems. Zbl 07678783
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav
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
Time- and space-optimal algorithm for the many-visits TSP. Zbl 1483.68508
Berger, André; Kozma, László; Mnich, Matthias; Vincze, Roland
3
2020
Random walks on small world networks. Zbl 1484.05195
Dyer, Martin E.; Galanis, Andreas; Goldberg, Leslie Ann; Jerrum, Mark; Vigoda, Eric
3
2020
Randomized memoryless algorithms for the weighted and the generalized \(k\)-server problems. Zbl 1484.68340
Chiplunkar, Ashish; Vishwanathan, Sundar
3
2020
Fine-grained complexity analysis of two classic TSP variants. Zbl 07471490
de Berg, Mark; Buchin, Kevin; Jansen, Bart M. P.; Woeginger, Gerhard
3
2020
Submatrix maximum queries in Monge and partial Monge matrices are equivalent to predecessor search. Zbl 1484.68055
Gawrychowski, Paweł; Mozes, Shay; Weimann, Oren
2
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.
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
Improved dynamic graph coloring. Zbl 1484.68172
Solomon, Shay; Wein, Nicole
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
Tree edit distance cannot be computed in strongly subcubic time (unless APSP can). Zbl 1527.68045
Bringmann, Karl; Gawrychowski, Paweł; Mozes, Shay; Weimann, Oren
2
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
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
Subexponential algorithms for rectilinear Steiner tree and arborescence problems. Zbl 1484.68159
Fomin, Fedor V.; Lokshtanov, Daniel; Kolay, Sudeshna; Panolan, Fahad; Saurabh, Saket
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
Dynamic parameterized problems and algorithms. Zbl 07678777
Alman, Josh; Mnich, Matthias; Williams, Virginia Vassilevska
1
2020
Point-width and max-CSPs. Zbl 07678786
Carbonnel, Clément; Romero, Miguel; Živný, Stanislav
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
21
2019
Faster pseudopolynomial time algorithms for subset sum. Zbl 1454.90076
Koiliaris, Konstantinos; Xu, Chao
20
2019
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
20
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
14
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
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
Domination when the stars are out. Zbl 1454.68104
Hermelin, Danny; Mnich, Matthias; Van Leeuwen, Erik Jan; Woeginger, Gerhard
11
2019
Efficient algorithms for constructing very sparse spanners and emulators. Zbl 1435.68378
Elkin, Michael; Neiman, Ofer
9
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
9
2019
Beating approximation factor two for weighted tree augmentation with bounded costs. Zbl 1454.68085
Adjiashvili, David
9
2019
Exponential separations in the energy complexity of leader election. Zbl 1454.68015
Chang, Yi-Jun; Kopelowitz, Tsvi; Pettie, Seth; Wang, Ruosong; Zhan, Wei
7
2019
Deterministic graph exploration with advice. Zbl 1454.68102
Gorain, Barun; Pelc, Andrzej
7
2019
Completeness for first-order properties on sparse structures with algorithmic applications. Zbl 1454.68054
Gao, Jiawei; Impagliazzo, Russell; Kolokolova, Antonina; Williams, Ryan
7
2019
...and 595 more Documents
all top 5

Cited by 5,897 Authors

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

Cited in 308 Journals

527 Theoretical Computer Science
470 Algorithmica
165 Discrete Applied Mathematics
143 SIAM Journal on Computing
128 Journal of Computer and System Sciences
119 Theory of Computing Systems
102 Information Processing Letters
101 Journal of Combinatorial Optimization
97 SIAM Journal on Discrete Mathematics
66 Distributed Computing
64 Computational Geometry
59 Information and Computation
59 Journal of Discrete Algorithms
55 Discrete & Computational Geometry
53 Mathematical Programming. Series A. Series B
42 European Journal of Operational Research
32 Mathematics of Operations Research
32 Discrete Optimization
31 Journal of Scheduling
30 ACM Journal of Experimental Algorithmics
30 ACM Transactions on Algorithms
28 Journal of Graph Algorithms and Applications
27 Discrete Mathematics
27 Operations Research Letters
27 Computers & Operations Research
27 Random Structures & Algorithms
26 Algorithms
23 Artificial Intelligence
23 Journal of Combinatorial Theory. Series B
21 Networks
21 The Electronic Journal of Combinatorics
20 Annals of Operations Research
19 Information Sciences
19 Discrete Mathematics, Algorithms and Applications
18 International Journal of Foundations of Computer Science
17 Journal of Global Optimization
15 Operations Research
15 European Journal of Combinatorics
15 Journal of Machine Learning Research (JMLR)
14 Journal of Graph Theory
14 Graphs and Combinatorics
14 Games and Economic Behavior
14 Optimization Letters
12 International Journal of Computational Geometry & Applications
12 SIAM Journal on Optimization
12 Computer Science Review
11 Acta Informatica
11 INFORMS Journal on Computing
10 Journal of Symbolic Computation
10 Combinatorics, Probability and Computing
10 Journal of the ACM
10 Data Mining and Knowledge Discovery
9 Linear Algebra and its Applications
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 SIAM Journal on Scientific Computing
6 Logical Methods in Computer Science
6 Theory of Computing
5 Applied Mathematics and Computation
5 Journal of Combinatorial Theory. Series A
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 Mathematical Methods of Operations Research
5 RAIRO. 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 Combinatorica
4 International Journal of Approximate Reasoning
4 International Journal of Computer Mathematics
4 Cybernetics and Systems Analysis
4 Annals of Mathematics and Artificial Intelligence
4 Electronic Journal of Probability
4 International Journal of Applied Mathematics and Computer Science
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 Applied Probability
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
...and 208 more Journals
all top 5

Cited in 51 Fields

3,524 Computer science (68-XX)
1,550 Combinatorics (05-XX)
1,094 Operations research, mathematical programming (90-XX)
381 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
109 Numerical analysis (65-XX)
103 Statistics (62-XX)
84 Information and communication theory, circuits (94-XX)
78 Probability theory and stochastic processes (60-XX)
70 Biology and other natural sciences (92-XX)
67 Convex and discrete geometry (52-XX)
47 Number theory (11-XX)
35 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)
19 Quantum theory (81-XX)
17 Systems theory; control (93-XX)
13 Calculus of variations and optimal control; optimization (49-XX)
12 Manifolds and cell complexes (57-XX)
11 Group theory and generalizations (20-XX)
11 Algebraic topology (55-XX)
10 Dynamical systems and ergodic theory (37-XX)
10 Statistical mechanics, structure of matter (82-XX)
8 Commutative algebra (13-XX)
8 Geometry (51-XX)
8 General topology (54-XX)
5 General algebraic systems (08-XX)
5 Algebraic geometry (14-XX)
5 Functions of a complex variable (30-XX)
5 Approximations and expansions (41-XX)
5 Fluid mechanics (76-XX)
4 General and overarching topics; collections (00-XX)
3 History and biography (01-XX)
3 Measure and integration (28-XX)
3 Partial differential equations (35-XX)
3 Differential geometry (53-XX)
2 Category theory; homological algebra (18-XX)
2 Real functions (26-XX)
2 Difference and functional equations (39-XX)
1 Field theory and polynomials (12-XX)
1 Associative rings and algebras (16-XX)
1 Topological groups, Lie groups (22-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 particles and systems (70-XX)
1 Mechanics of deformable solids (74-XX)
1 Relativity and gravitational theory (83-XX)
1 Mathematics education (97-XX)

Citations by Year