×

zbMATH — the first resource for mathematics

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
Documents Indexed: 724 Publications (since 2005)
References Indexed: 14 Publications with 412 References.
all top 5

Authors

22 Saurabh, Saket
20 Lokshtanov, Daniel
14 Fomin, Fedor V.
14 Hajiaghayi, Mohammad Taghi
13 Kortsarz, Guy
13 Marx, Dániel
10 Tarjan, Robert Endre
9 Agarwal, Pankaj Kumar
9 Kaplan, Haim
9 Thorup, Mikkel
9 Zwick, Uri
8 Chan, Timothy Moon-Yew
8 Demaine, Erik D.
8 Nutov, Zeev
7 Chan, T.-H. Hubert
7 Cygan, Marek
7 Elkin, Michael
7 Eppstein, David Arthur
7 Gupta, Anupam
7 Halldórsson, Magnús Mar
7 Navarro, Gonzalo
7 Pelc, Andrzej
7 Peleg, David
7 Pettie, Seth
7 Sharir, Micha
7 Solomon, Shay
7 Sviridenko, Maxim I.
7 Yi, Ke
6 Alon, Noga M.
6 Bansal, Nikhil
6 Gabow, Harold N.
6 Grandoni, Fabrizio
6 Har-Peled, Sariel
6 Harris, David G.
6 Khandekar, Rohit
6 Lewenstein, Moshe
6 Nagarajan, Viswanath
6 Pilipczuk, Michał
6 Raman, Venkatesh
6 Salavatipour, Mohammad R.
5 Aronov, Boris
5 Azar, Yossi
5 Chekuri, Chandra S.
5 Cormode, Graham
5 Gørtz, Inge Li
5 Klein, Philip N.
5 Munro, J. Ian
5 Naor, Joseph Seffi
5 Panolan, Fahad
5 Pilipczuk, Marcin L.
5 Pruhs, Kirk R.
5 Roditty, Liam
5 Ron, Dana
5 Rosén, Adi
5 Rutter, Ignaz
5 Schieber, Baruch
5 Shachnai, Hadas
5 Srinivasan, Aravind
5 Weimann, Oren
5 Yuster, Raphael
5 Zehavi, Meirav
4 Borradaile, Glencora
4 Cabello, Sergio
4 Chan, Ho-Leung
4 Czumaj, Artur
4 Even, Guy
4 Farach-Colton, Martin
4 Feldman, Moran
4 Ferragina, Paolo
4 Friggstad, Zachary
4 Georgiadis, Loukas
4 Goel, Ashish
4 Guha, Sudipto
4 Haeupler, Bernhard
4 He, Meng
4 Husfeldt, Thore
4 Kaski, Petteri
4 Kavitha, Telikepalli
4 Khanna, Sanjeev
4 Khuller, Samir
4 Korman, Amos
4 Levin, Asaf
4 Mäkinen, Veli
4 Mathieu, Claire
4 Mehlhorn, Kurt
4 Mozes, Shay
4 Rabani, Yuval
4 Racke, Harald
4 Ramanujan, M. S.
4 Saberi, Amin
4 Satti, Srinivasa Rao
4 Svensson, Ola
4 Swamy, Chaitanya
4 Szpankowski, Wojciech
4 Thilikos, Dimitrios M.
4 Van Leeuwen, Erik Jan
4 Vassilevska Williams, Virginia
3 Abraham, Ittai
3 Albers, Susanne
3 Alonso, Laurent
...and 1,137 more Authors

Publications by Year

Citations contained in zbMATH Open

543 Publications have been cited 3,457 times in 2,709 Documents Cited by Year
Compressed representations of sequences and full-text indexes. Zbl 1321.68263
Ferragina, Paolo; Manzini, Giovanni; Mäkinen, Veli; Navarro, Gonzalo
125
2007
Algorithmic construction of sets for \(k\)-restrictions. Zbl 1321.68445
Alon, Noga; Moshkovitz, Dana; Safra, Shmuel
65
2006
Cache-oblivious algorithms. Zbl 1295.68236
Frigo, Matteo; Leiserson, Charles E.; Prokop, Harald; Ramachandran, Sridhar
54
2012
Coresets, sparse greedy approximation, and the Frank-Wolfe algorithm. Zbl 1300.90026
Clarkson, Kenneth L.
47
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
43
2007
Tight bounds for worst-case equilibria. Zbl 1322.91017
Czumaj, Artur; Vöcking, Berthold
42
2007
A \(4k^2\) kernel for feedback vertex set. Zbl 1300.05236
Thomassé, Stéphan
40
2010
Fully functional static and dynamic succinct trees. Zbl 1333.68084
Navarro, Gonzalo; Sadakane, Kunihiko
40
2014
Convergence time to Nash equilibrium in load balancing. Zbl 1192.68956
Even-Dar, Eyal; Kesselman, Alex; Mansour, Yishay
39
2007
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.
39
2005
Faster parameterized algorithms using linear programming. Zbl 1398.68254
Lokshtanov, Daniel; Narayanaswamy, N. S.; Raman, Venkatesh; Ramanujan, M. S.; Saurabh, Saket
34
2014
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.
31
2008
Finding small separators in linear time via treewidth reduction. Zbl 1301.05337
Marx, Dániel; O’Sullivan, Barry; Razgon, Igor
30
2013
Multicommodity demand flow in a tree and packing integer programs. Zbl 1192.68879
Chekuri, Chandra; Mydlarz, Marcelo; Shepherd, F. Bruce
26
2007
Computing almost shortest paths. Zbl 1321.05258
Elkin, Michael
25
2005
Kernelization lower bounds through colors and IDs. Zbl 1398.68226
Dom, Michael; Lokshtanov, Daniel; Saurabh, Saket
25
2014
How to meet asynchronously (almost) everywhere. Zbl 1295.68171
Czyzowicz, Jurek; Pelc, Andrzej; Labourel, Arnaud
24
2012
Succinct ordinal trees with level-ancestor queries. Zbl 1321.68223
Geary, Richard F.; Raman, Rajeev; Raman, Venkatesh
24
2006
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
24
2016
Nearest-neighbor-preserving embeddings. Zbl 1192.68748
Indyk, Piotr; Naor, Assaf
23
2007
Additive spanners and \(({\alpha}, {\beta})\)-spanners. Zbl 1295.05094
Baswana, Surender; Kavitha, Telikepalli; Mehlhorn, Kurt; Pettie, Seth
23
2010
A better approximation ratio for the vertex cover problem. Zbl 1298.68295
Karakostas, George
22
2009
Maintaining information in fully dynamic trees with top trees. Zbl 1321.68211
Alstrup, Stephen; Holm, Jacob; Lichtenberg, Kristian De; Thorup, Mikkel
22
2005
The relative worst order ratio for online algorithms. Zbl 1321.68512
Boyar, Joan; Favrholdt, Lene M.
21
2007
Novel architectures for P2P applications: the continuous-discrete approach. Zbl 1192.68050
Naor, Moni; Wieder, Udi
20
2007
Achieving anonymity via clustering. Zbl 1300.68023
Aggarwal, Gagan; Panigrahy, Rina; Feder, Tomás; Thomas, Dilys; Kenthapadi, Krishnaram; Khuller, Samir; Zhu, An
20
2010
Speed scaling with an arbitrary power function. Zbl 1301.90026
Bansal, Nikhil; Chan, Ho-Leung; Pruhs, Kirk
20
2013
Faster fixed parameter tractable algorithms for finding feedback vertex sets. Zbl 1321.05275
Raman, Venkatesh; Saurabh, Saket; Subramanian, C. R.
20
2006
Approximate distance oracles for unweighted graphs in expected \(O(n^2)\) time. Zbl 1321.68214
Baswana, Surender; Sen, Sandeep
19
2006
A general approach to online network optimization problems. Zbl 1321.68509
Alon, Noga; Awerbuch, Baruch; Azar, Yossi; Buchbinder, Niv; Naor, Joseph (Seffi)
19
2006
Succinct indexes for strings, binary relations and multilabeled trees. Zbl 1295.68227
Barbay, Jérémy; He, Meng; Munro, J. Ian; Satti, Srinivasa Rao
18
2011
Fully compressed suffix trees. Zbl 1295.68103
Russo, Luís M. S.; Navarro, Gonzalo; Oliveira, Arlindo L.
18
2011
Delays induce an exponential memory gap for rendezvous in trees. Zbl 1301.68203
Fraigniaud, Pierre; Pelc, Andrzej
18
2013
Bipartite roots of graphs. Zbl 1321.05209
Lau, Lap Chi
18
2006
Quasiconvex analysis of multivariate recurrence equations for backtracking algorithms. Zbl 1321.68558
Eppstein, David
18
2006
Rank-maximal matchings. Zbl 1321.90116
Irving, Robert W.; Kavitha, Telikepalli; Mehlhorn, Kurt; Michail, Dimitrios; Paluch, Katarzyna E.
18
2006
Gathering despite mischief. Zbl 1398.68054
Dieudonné, Yoann; Pelc, Andrzej; Peleg, David
18
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
17
2010
Compressed indexes for dynamic text collections. Zbl 1321.68261
Chan, Ho-Leung; Hon, Wing-Kai; Lam, Tak-Wah; Sadakane, Kunihiko
17
2007
Energy-efficient algorithms for flow time minimization. Zbl 1445.68036
Albers, Susanne; Fujiwara, Hiroshi
17
2007
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
16
2012
Minimizing movement. Zbl 1298.68293
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Mahini, Hamid; Sayedi-Roshkhar, Amin S.; Oveisgharan, Shayan; Zadimoghaddam, Morteza
16
2009
Low distortion spanners. Zbl 1298.05307
Pettie, Seth
16
2009
On a generalization of the stable roommates problem. Zbl 1321.05201
Cechlárová, Katarína; Fleiner, Tamás
16
2005
Approximation algorithms and hardness results for cycle packing problems. Zbl 1446.68121
Krivelevich, Michael; Nutov, Zeev; Salavatipour, Mohammad R.; Verstraete, Jacques; Yuster, Raphael
16
2007
Fully dynamic algorithms for chordal graphs and split graphs. Zbl 1445.05103
Ibarra, Louis
16
2008
Approximating rank-width and clique-width quickly. Zbl 1451.05231
Oum, Sang-Il
16
2008
The price of anarchy in network creation games. Zbl 1295.68041
Demaine, Erik D.; Hajiaghayi, Mohammadtaghi; Mahini, Hamid; Zadimoghaddam, Morteza
15
2012
An \(O(n\log n)\) approximation scheme for Steiner tree in planar graphs. Zbl 1300.05294
Borradaile, Glencora; Klein, Philip; Mathieu, Claire
15
2009
Approximating minimum-cost connectivity problems via uncrossable bifamilies. Zbl 1301.68275
Nutov, Zeev
15
2012
The string edit distance matching problem with moves. Zbl 1321.68551
Cormode, Graham; Muthukrishnan, S.
15
2007
Deterministic conflict-free coloring for intervals: from offline to online. Zbl 1445.68357
Bar-Noy, Amotz; Cheilaris, Panagiotis; Smorodinsky, Shakhar
15
2008
Deterministic rendezvous, treasure hunts, and strongly universal exploration sequences. Zbl 1333.68216
Ta-Shma, Amnon; Zwick, Uri
15
2014
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
14
2010
On exact algorithms for Treewidth. Zbl 1301.05328
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
14
2012
A linear-time approximation algorithm for weighted matchings in graphs. Zbl 1321.05279
Vinkemeier, Doratha E. Drake; Hougardy, Stefan
14
2005
Improved algorithms for weakly chordal graphs. Zbl 1321.05265
Hayward, Ryan B.; Spinrad, Jeremy P.; Sritharan, R.
14
2007
Compression via matroids: a randomized polynomial kernel for odd cycle transversal. Zbl 1398.68250
Kratsch, Stefan; Wahlström, Magnus
14
2014
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
14
2016
Algorithms for power savings. Zbl 1422.68018
Irani, Sandy; Shukla, Sandeep; Gupta, Rajesh
14
2007
Improved approximation results for the stable marriage problem. Zbl 1192.68903
Halldórsson, Magnús M.; Iwama, Kazuo; Miyazaki Shuichi; Yanagisawa, Hiroki
13
2007
Tree exploration with logarithmic memory. Zbl 1295.68203
Ambühl, Christoph; Gąsieniec, Leszek; Pelc, Andrzej; Radzik, Tomasz; Zhang, Xiaohui
13
2011
Improved algorithms for orienteering and related problems. Zbl 1295.05225
Chekuri, Chandra; Korula, Nitish; Pál, Martin
13
2012
An almost optimal unrestricted fast Johnson-Lindenstrauss transform. Zbl 1301.68233
Ailon, Nir; Liberty, Edo
13
2013
Simultaneous PQ-ordering with applications to constrained embedding problems. Zbl 1398.68387
Bläsius, Thomas; Rutter, Ignaz
13
2016
Approximate parameterized matching. Zbl 1192.68828
Hazay, Carmit; Lewenstein, Moshe; Sokol, Dina
12
2007
Scalably scheduling processes with arbitrary speedup curves. Zbl 1295.68048
Edmonds, Jeff; Pruhs, Kirk
12
2012
Fully dynamic randomized algorithms for graph spanners. Zbl 1295.05221
Baswana, Surender; Khurana, Sumeet; Sarkar, Soumojit
12
2012
An optimal decomposition algorithm for tree edit distance. Zbl 1300.68057
Demaine, Erik D.; Mozes, Shay; Rossman, Benjamin; Weimann, Oren
12
2009
Comparison-based time-space lower bounds for selection. Zbl 1300.68032
Chan, Timothy M.
12
2010
Approximating fractional hypertree width. Zbl 1300.05201
Marx, Dániel
12
2010
Optimal constrained graph exploration. Zbl 1321.68382
Duncan, Christian A.; Kobourov, Stephen G.; Kumar, V. S. Anil
12
2006
Dynamic text and static pattern matching. Zbl 1321.68547
Amir, Amihood; Landau, Gad M.; Lewenstein, Moshe; Sokol, Dina
12
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
12
2017
The priority R-tree: a practically efficient and worst-case optimal R-tree. Zbl 1445.68060
Arge, Lars; de Berg, Mark; Haverkort, Herman; Yi, Ke
12
2008
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
12
2008
Structure and linear-time recognition of 4-leaf powers. Zbl 1451.05040
Brandstädt, Andreas; Le, Van Bang; Sritharan, R.
12
2008
Approximation algorithms for computing maximin share allocations. Zbl 1407.68540
Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin
12
2017
Known algorithms on graphs of bounded treewidth are probably optimal. Zbl 1454.68110
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket
12
2018
Taxes for linear atomic congestion games. Zbl 1295.91006
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis
11
2010
Set connectivity problems in undirected graphs and the directed Steiner network problem. Zbl 1295.68211
Chekuri, Chandra; Even, Guy; Gupta, Anupam; Segev, Danny
11
2011
Adversarial queuing on the multiple access channel. Zbl 1295.68047
Chlebus, Bogdan S.; Kowalski, Dariusz R.; Rokicki, Mariusz A.
11
2012
Low-dimensional lattice basis reduction revisited. Zbl 1300.11133
Nguyen, Phong Q.; Stehlé, Damien
11
2009
Optimizing throughput and energy in online deadline scheduling. Zbl 1300.90013
Chan, Ho-Leung; Chan, Joseph Wun-Tat; Lam, Tak-Wah; Lee, Lap-Kei; Mak, Kin-Sum; Wong, Prudence W. H.
11
2009
Optimization problems in multiple-interval graphs. Zbl 1300.05295
Butman, Ayelet; Hermelin, Danny; Lewenstein, Moshe; Rawitz, Dror
11
2010
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error. Zbl 1301.68162
Jayram, T. S.; Woodruff, David P.
11
2013
A logarithmic approximation for unsplittable flow on line graphs. Zbl 1321.68493
Bansal, Nikhil; Friggstad, Zachary; Khandekar, Rohit; Salavatipour, Mohammad R.
11
2014
Fast sparse matrix multiplication. Zbl 1321.65073
Yuster, Raphael; Zwick, Uri
11
2005
On network design problems: fixed cost flows and the covering Steiner problem. Zbl 1321.68021
Even, Guy; Kortsarz, Guy; Slany, Wolfgang
11
2005
Optimal branch-decomposition of planar graphs in \(O(n^3)\) time. Zbl 1445.68165
Gu, Qian-Ping; Tamaki, Hisao
11
2008
Getting the best response for your erg. Zbl 1445.68041
Pruhs, Kirk; Uthaisombut, Patchrawat; Woeginger, Gerhard
11
2008
Decision trees for entity identification, approximation algorithms and hardness results. Zbl 1295.68210
Chakaravarthy, Venkatesan T.; Pandit, Vinayaka; Roy, Sambuddha; Awasthi, Pranjal; Mohania, Mukesh K.
10
2011
Algorithms for distributed functional monitoring. Zbl 1295.68204
Cormode, Graham; Muthukrishnan, S.; Yi, Ke
10
2011
Minimizing movement in mobile facility location problems. Zbl 1295.90019
Friggstad, Zachary; Salavatipour, Mohammad R.
10
2011
An improved approximation algorithm for Resource Allocation. Zbl 1295.68209
Calinescu, Gruia; Chakrabarti, Amit; Karloff, Howard; Rabani, Yuval
10
2011
Santa Claus meets hypergraph matchings. Zbl 1295.05165
Asadpour, Arash; Feige, Uriel; Saberi, Amin
10
2012
Succinct ordinal trees based on tree covering. Zbl 1295.68102
He, Meng; Munro, J. Ian; Satti, Srinivasa Rao
10
2012
Range searching on uncertain data. Zbl 1295.68098
Agarwal, Pankaj K.; Cheng, Siu-Wing; Yi, Ke
10
2012
Maximal biconnected subgraphs of random planar graphs. Zbl 1300.05287
Panagiotou, Konstantinos; Steger, Angelika
10
2010
Mechanism design for fractional scheduling on unrelated machines. Zbl 1300.90014
Christodoulou, George; Koutsoupias, Elias; Kovács, Annamária
10
2010
Enumerating minimal dominating sets in \(K_t\)-free graphs and variants. Zbl 07342482
Bonamy, Marthe; Defrain, Oscar; Heinrich, Marc; Pilipczuk, Michał; Raymond, Jean-Florent
4
2020
Proximity results and faster algorithms for integer programming using the Steinitz lemma. Zbl 1454.90029
Eisenbrand, Friedrich; Weismantel, Robert
2
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
2
2020
A linear-time algorithm for seeds computation. Zbl 07342470
Kociumaka, Tomasz; Kubica, Marcin; Radoszewski, Jakub; Rytter, Wojciech; Waleń, Tomasz
2
2020
Solving the sigma-tau problem. Zbl 1458.05108
Sawada, Joe; Williams, Aaron
1
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
1
2020
Linear-time string indexing and analysis in small space. Zbl 07342460
Belazzougui, Djamal; Cunial, Fabio; Kärkkäinen, Juha; Mäkinen, Veli
1
2020
Periods of iterations of functions with restricted preimage sizes. Zbl 07342473
Martins, Rodrigo S. V.; Panario, Daniel; Qureshi, Claudio; Schmutz, Eric
1
2020
On problems equivalent to \((\min,+)\)-convolution. Zbl 1454.68052
Cygan, Marek; Mucha, Marcin; Węgrzycki, Karol; Włodarczyk, Michał
6
2019
Feedback vertex set inspired kernel for chordal vertex deletion. Zbl 1454.68088
Agrawal, Akanksha; Lokshtanov, Daniel; Misra, Pranabendu; Saurabh, Saket; Zehavi, Meirav
4
2019
Domination when the stars are out. Zbl 1454.68104
Hermelin, Danny; Mnich, Matthias; Van Leeuwen, Erik Jan; Woeginger, Gerhard
3
2019
Fully polynomial FPT algorithms for some classes of bounded clique-width graphs. Zbl 1454.68098
Coudert, David; Ducoffe, Guillaume; Popa, Alexandru
3
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
3
2019
Efficient algorithms for constructing very sparse spanners and emulators. Zbl 1435.68378
Elkin, Michael; Neiman, Ofer
3
2019
Subquadratic algorithms for the diameter and the sum of pairwise distances in planar graphs. Zbl 1443.68122
Cabello, Sergio
3
2019
Derandomized concentration bounds for polynomials, and hypergraph maximal independent set. Zbl 1455.68272
Harris, David G.
2
2019
Recognizing weak embeddings of graphs. Zbl 1454.68089
Akitaya, Hugo A.; Fulek, Radoslav; Tóth, Csaba D.
2
2019
Heavy hitters and the structure of local privacy. Zbl 1454.68042
Bun, Mark; Nelson, Jelani; Stemmer, Uri
2
2019
The complexity of independent set reconfiguration on bipartite graphs. Zbl 1454.68111
Lokshtanov, Daniel; Mouawad, Amer E.
2
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
2
2019
Completeness for first-order properties on sparse structures with algorithmic applications. Zbl 1454.68054
Gao, Jiawei; Impagliazzo, Russell; Kolokolova, Antonina; Williams, Ryan
2
2019
The \((h,k)\)-server problem on bounded depth trees. Zbl 1454.68189
Bansal, Nikhil; Eliéš, Marek; Jeż, Łukasz; Koumoutsos, Grigorios
1
2019
Online submodular maximization with preemption. Zbl 1453.68216
Buchbinder, Niv; Feldman, Moran; Schwartz, Roy
1
2019
Sparse approximation via generating point sets. Zbl 1454.68154
Blum, Avrim; Har-Peled, Sariel; Raichel, Benjamin
1
2019
Ascending-price algorithms for unknown markets. Zbl 1458.91087
Bei, Xiaohui; Garg, Jugal; Hoefer, Martin
1
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
1
2019
Distributed dominating set approximations beyond planar graphs. Zbl 1454.68090
Amiri, Saeed Akhoondian; Schmid, Stefan; Siebertz, Sebastian
1
2019
Faster pseudopolynomial time algorithms for subset sum. Zbl 1454.90076
Koiliaris, Konstantinos; Xu, Chao
1
2019
Dynamic beats fixed: on phase-based algorithms for file migration. Zbl 1441.68292
Bienkowski, Marcin; Byrka, Jarosław; Mucha, Marcin
1
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.
1
2019
Entropy and optimal compression of some general plane trees. Zbl 1454.68047
Gołębiewski, Zbigniew; Magner, Abram; Szpankowski, Wojciech
1
2019
Deterministic graph exploration with advice. Zbl 1454.68102
Gorain, Barun; Pelc, Andrzej
1
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
1
2019
Known algorithms on graphs of bounded treewidth are probably optimal. Zbl 1454.68110
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket
12
2018
Deterministic truncation of linear matroids. Zbl 1440.68128
Lokshtanov, Daniel; Misra, Pranabendu; Panolan, Fahad; Saurabh, Saket
8
2018
Deterministic algorithms for submodular maximization problems. Zbl 1454.68170
Buchbinder, Niv; Feldman, Moran
6
2018
Scaling algorithms for weighted matching in general graphs. Zbl 1451.05227
Duan, Ran; Pettie, Seth; Su, Hsin-Hao
5
2018
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
5
2018
Data structures for weighted matching and extensions to \(b\)-matching and \(f\)-factors. Zbl 1454.68030
Gabow, Harold N.
5
2018
Exploring the complexity of layout parameters in tournaments and semicomplete digraphs. Zbl 1454.68055
Barbero, Florian; Paul, Christophe; Pilipczuk, MichaŁ
4
2018
Network sparsification for Steiner problems on planar and bounded-genus graphs. Zbl 1454.68114
Pilipczuk, Marcin; Pilipczuk, Michał; Sankowski, Piotr; van Leeuwen, Erik Jan
3
2018
Linear time parameterized algorithms for Subset Feedback Vertex Set. Zbl 1440.68139
Lokshtanov, Daniel; Ramanujan, M. S.; Saurabh, Saket
3
2018
Fault-tolerant approximate BFS structures. Zbl 1422.68193
Parter, Merav; Peleg, David
3
2018
Near-optimal light spanners. Zbl 1457.05029
Chechik, Shiri; Wulff-Nilsen, Christian
3
2018
Graph reconstruction and verification. Zbl 1454.68106
Kannan, Sampath; Mathieu, Claire; Zhou, Hang
2
2018
Dynamic time warping and geometric edit distance: breaking the quadratic barrier. Zbl 1441.68303
Gold, Omer; Sharir, Micha
2
2018
Packing groups of items into multiple knapsacks. Zbl 1454.68178
Chen, Lin; Zhang, Guochuan
2
2018
Independence and efficient domination on \(P_6\)-free graphs. Zbl 1431.68049
Lokshtanov, Daniel; Pilipczuk, Marcin; Leeuwen, Erik Jan Van
2
2018
Primal dual gives almost optimal energy-efficient online algorithms. Zbl 1421.68242
Devanur, Nikhil R.; Huang, Zhiyi
2
2018
Kernels for (connected) dominating set on graphs with excluded topological minors. Zbl 1455.68072
Fomin, Fedor V.; Lokshtanov, Daniel; Saurabh, Saket; Thilikos, Dimitrios M.
2
2018
Efficient computation of middle levels Gray codes. Zbl 1414.94947
Mütze, Torsten; Nummenpalo, Jerri
2
2018
Subexponential parameterized algorithm for {Interval Completion}. Zbl 1454.68094
Bliznets, Ivan; Fomin, Fedor V.; Pilipczuk, Marcin; Pilipczuk, Michał
2
2018
Batched point location in SINR diagrams via algebraic tools. Zbl 1454.68152
Aronov, Boris; Katz, Matthew J.
1
2018
Streaming algorithms for estimating the matching size in planar graphs and beyond. Zbl 1454.68191
Esfandiari, Hossein; Hajiaghayi, Mohammadtaghi; Liaghat, Vahid; Monemizadeh, Morteza; Onak, Krzysztof
1
2018
Windrose planarity: embedding graphs with direction-constrained edges. Zbl 1454.68091
Angelini, Patrizio; Da Lozzo, Giordano; Di Battista, Giuseppe; Di Donato, Valentino; Kindermann, Philipp; Rote, Günter; Rutter, Ignaz
1
2018
The parametric closure problem. Zbl 1445.68066
Eppstein, David
1
2018
Binary adder circuits of asymptotically minimum depth, linear size, and fan-out two. Zbl 1451.68105
Held, Stephan; Spirkl, Sophie Theresa
1
2018
Selection and sorting in the “restore” model. Zbl 1421.68032
Chan, Timothy M.; Munro, J. Ian; Raman, Venkatesh
1
2018
Approximation algorithms for minimum-load \(k\)-facility location. Zbl 1454.68175
Ahmadian, Sara; Behsaz, Babak; Friggstad, Zachary; Jorati, Amin; Salavatipour, Mohammad R.; Swamy, Chaitanya
1
2018
Randomized embeddings with slack and high-dimensional approximate nearest neighbor. Zbl 1454.68037
Anagnostopoulos, Evangelos; Emiris, Ioannis Z.; Psarros, Ioannis
1
2018
Distributed online and stochastic queueing on a multiple access channel. Zbl 1454.68017
Bienkowski, Marcin; Jurdzinski, Tomasz; Korzeniowski, Miroslaw; Kowalski, Dariusz R.
1
2018
Computing the Gromov-Hausdorff distance for metric trees. Zbl 1454.68174
Agarwal, Pankaj K.; Fox, Kyle; Nath, Abhinandan; Sidiropoulos, Anastasios; Wang, Yusu
1
2018
Faster algorithms for computing plurality points. Zbl 1454.68156
de Berg, Mark; Gudmundsson, Joachim; Mehr, Mehran
1
2018
Erratum: “Approximating minimum-cost connectivity problems via uncrossable bifamilies”. Zbl 1454.68186
Nutov, Zeev
1
2018
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
12
2017
Approximation algorithms for computing maximin share allocations. Zbl 1407.68540
Amanatidis, Georgios; Markakis, Evangelos; Nikzad, Afshin; Saberi, Amin
12
2017
Uniform kernelization complexity of hitting forbidden minors. Zbl 1440.68137
Giannopoulou, Archontia C.; Jansen, Bart M. P.; Lokshtanov, Daniel; Saurabh, Saket
6
2017
On uniform capacitated \(k\)-median beyond the natural LP relaxation. Zbl 1451.90089
Li, Shi
4
2017
Generating random permutations by coin tossing: classical algorithms, new analysis, and modern implementation. Zbl 1445.68104
Bacher, Axel; Bodini, Olivier; Hwang, Hsien-Kuei; Tsai, Tsung-Hsi
4
2017
Combinatorial algorithm for restricted max-min fair allocation. Zbl 1446.91043
Annamalai, Chidambaram; Kalaitzis, Christos; Svensson, Ola
4
2017
Time vs. information tradeoffs for leader election in anonymous trees. Zbl 1445.68032
Glacet, Christian; Miller, Avery; Pelc, Andrzej
4
2017
Dynamic facility location via exponential clocks. Zbl 1451.90084
An, Hyung-Chan; Norouzi-Fard, Ashkan; Svensson, Ola
3
2017
Asymptotically optimal encodings of range data structures for selection and top-\(k\) queries. Zbl 1445.68067
Grossi, Roberto; Iacono, John; Navarro, Gonzalo; Raman, Rajeev; Satti, S. Rao
3
2017
Submatrix maximum queries in Monge matrices and partial Monge matrices, and their applications. Zbl 1446.68041
Kaplan, Haim; Mozes, Shay; Nussbaum, Yahav; Sharir, Micha
3
2017
Representative families of product families. Zbl 1445.68330
Fomin, Fedor V.; Lokshtanov, Daniel; Panolan, Fahad; Saurabh, Saket
3
2017
Smoothed analysis of local search for the maximum-cut problem. Zbl 1421.68152
Etscheid, Michael; Röglin, Heiko
2
2017
For-all sparse recovery in near-optimal time. Zbl 1446.68196
Gilbert, Anna C.; Li, Yi; Porat, Ely; Strauss, Martin J.
2
2017
Maximizing symmetric submodular functions. Zbl 1452.90263
Feldman, Moran
2
2017
Discovering archipelagos of tractability for constraint satisfaction and counting. Zbl 1446.68073
Ganian, Robert; Ramanujan, M. S.; Szeider, Stefan
1
2017
Algorithmic and enumerative aspects of the Moser-Tardos distribution. Zbl 1445.05107
Harris, David G.; Srinivasan, Aravind
1
2017
Faster and simpler sketches of valuation functions. Zbl 1446.68195
Cohavi, Keren; Dobzinski, Shahar
1
2017
Max-sum diversification, monotone submodular functions, and dynamic updates. Zbl 1452.68273
Borodin, Allan; Jain, Aadhar; Lee, Hyun Chul; Ye, Yuli
1
2017
Hollow heaps. Zbl 1440.68051
Hansen, Thomas Dueholm; Kaplan, Haim; Tarjan, Robert E.; Zwick, Uri
1
2017
Linear-time parameterized algorithms via skew-symmetric multicuts. Zbl 1422.68137
Ramanujan, M. S.; Saurabh, Saket
1
2017
Exact and asymptotic solutions of a divide-and-conquer recurrence dividing at half: theory and applications. Zbl 1451.68359
Hwang, Hsien-Kuei; Janson, Svante; Tsai, Tsung-Hsi
1
2017
Counting thin subgraphs via packings faster than meet-in-the-middle time. Zbl 1452.68133
Björklund, Andreas; Kaski, Petteri; Kowalik, Łukasz
1
2017
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
24
2016
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
14
2016
Simultaneous PQ-ordering with applications to constrained embedding problems. Zbl 1398.68387
Bläsius, Thomas; Rutter, Ignaz
13
2016
A simplified \(1.5\)-approximation algorithm for augmenting edge-connectivity of a graph from 1 to 2. Zbl 1398.68679
Kortsarz, Guy; Nutov, Zeev
10
2016
Point line cover: the easy kernel is essentially tight. Zbl 1423.68547
Kratsch, Stefan; Philip, Geevarghese; Ray, Saurabh
9
2016
Approximation algorithms for stochastic submodular set cover with applications to Boolean function evaluation and min-knapsack. Zbl 1421.68211
Deshpande, Amol; Hellerstein, Lisa; Kletenik, Devorah
8
2016
Nearest-neighbor searching under uncertainty. II. Zbl 1445.68076
Agarwal, Pankaj K.; Aronov, Boris; Har-Peled, Sariel; Phillips, Jeff M.; Yi, Ke; Zhang, Wuzhou
7
2016
Sorting and selection with imprecise comparisons. Zbl 1398.68113
Ajtai, Miklós; Feldman, Vitaly; Hassidim, Avinatan; Nelson, Jelani
6
2016
A new approach to incremental cycle detection and related problems. Zbl 1398.68386
Bender, Michael A.; Fineman, Jeremy T.; Gilbert, Seth; Tarjan, Robert E.
5
2016
Robust and max-min optimization under matroid and knapsack uncertainty sets. Zbl 1398.68689
Gupta, Anupam; Nagarajan, Viswanath; Ravi, R.
4
2016
A faster algorithm for computing straight skeletons. Zbl 1423.68542
Cheng, Siu-Wing; Mencel, Liam; Vigneron, Antoine
4
2016
Improved approximation algorithms for matroid and knapsack median problems and applications. Zbl 1446.68199
Swamy, Chaitanya
4
2016
On hierarchical routing in doubling metrics. Zbl 1445.68108
Chan, T.-H. Hubert; Gupta, Anupam; Maggs, Bruce M.; Zhou, Shuheng
4
2016
Lopsidependency in the Moser-Tardos framework: beyond the lopsided Lovász local lemma. Zbl 1446.68108
Harris, David G.
4
2016
...and 443 more Documents
all top 5

Cited by 3,928 Authors

59 Saurabh, Saket
50 Navarro, Gonzalo
31 Fomin, Fedor V.
31 Golovach, Petr A.
28 Pelc, Andrzej
27 Lokshtanov, Daniel
27 Raman, Venkatesh
26 Munro, J. Ian
25 Niedermeier, Rolf
23 Pilipczuk, Marcin L.
22 Gagie, Travis
22 Kratsch, Dieter
19 Jansen, Bart M. P.
18 Epstein, Leah
18 Paulusma, Daniël
18 Thankachan, Sharma V.
18 Zehavi, Meirav
16 Chan, Timothy Moon-Yew
16 He, Meng
16 Nutov, Zeev
15 Gawrychowski, Paweł
15 Hajiaghayi, Mohammad Taghi
15 Heggernes, Pinar
15 Kavitha, Telikepalli
15 Panolan, Fahad
15 Pilipczuk, Michał
15 Ramanujan, M. S.
15 Thilikos, Dimitrios M.
14 Komusiewicz, Christian
14 Marx, Dániel
14 Nekrich, Yakov
13 Cygan, Marek
13 Dieudonné, Yoann
13 Halldórsson, Magnús Mar
13 Nichterlein, André
13 Sadakane, Kunihiko
13 Sau, Ignasi
13 Shah, Rahul
12 Bilò, Davide
12 Hon, Wing-Kai
12 Nagarajan, Viswanath
12 Proietti, Guido
12 Villanger, Yngve
12 Wahlström, Magnus
11 Agrawal, Akanksha
11 Czyzowicz, Jurek
11 Fernau, Henning
11 Kärkkäinen, Juha
11 Kawarabayashi, Ken-ichi
11 Kratsch, Stefan
11 Leucci, Stefano
11 Moseley, Benjamin
11 Otachi, Yota
11 Puglisi, Simon J.
11 Shachnai, Hadas
11 Tamir, Tami
10 Bilò, Vittorio
10 Gaspers, Serge
10 Gutin, Gregory Z.
10 Kortsarz, Guy
10 Krithika, R.
10 Lampis, Michael
10 Larsen, Kim Skak
10 Levin, Asaf
10 Mozes, Shay
10 Pettie, Seth
10 Satti, Srinivasa Rao
9 Baswana, Surender
9 Bodlaender, Hans L.
9 Boyar, Joan F.
9 Demaine, Erik D.
9 Eppstein, David Arthur
9 Gualà, Luciano
9 Heuberger, Clemens
9 Im, Sungjin
9 López-Ortiz, Alejandro
9 Majumdar, Diptapriyo
9 Manurangsi, Pasin
9 Manzini, Giovanni
9 Peleg, David
9 Pissis, Solon P.
9 Rutter, Ignaz
9 Weimann, Oren
8 Aspnes, James
8 Barbay, Jérémy
8 Biró, Peter
8 Buchin, Kevin
8 Censor-Hillel, Keren
8 Da Lozzo, Giordano
8 Feldman, Moran
8 Fischer, Johannes
8 Fluschnik, Till
8 Fotakis, Dimitris A.
8 Gąsieniec, Leszek Antoni
8 Harks, Tobias
8 Huang, Chien-Chung
8 Jansen, Klaus
8 Kamiyama, Naoyuki
8 Kaplan, Haim
8 Klimm, Max
...and 3,828 more Authors
all top 5

Cited in 228 Journals

369 Theoretical Computer Science
348 Algorithmica
117 Discrete Applied Mathematics
100 SIAM Journal on Computing
98 Theory of Computing Systems
81 Information Processing Letters
75 Journal of Combinatorial Optimization
71 Journal of Computer and System Sciences
54 SIAM Journal on Discrete Mathematics
53 Distributed Computing
43 Journal of Discrete Algorithms
42 Computational Geometry
34 Discrete & Computational Geometry
34 Information and Computation
26 European Journal of Operational Research
26 Mathematical Programming. Series A. Series B
25 Mathematics of Operations Research
25 Journal of Scheduling
25 Algorithms
20 Discrete Mathematics
18 Discrete Optimization
15 Annals of Operations Research
15 International Journal of Foundations of Computer Science
15 Journal of Graph Algorithms and Applications
14 Operations Research Letters
13 Information Sciences
13 Computers & Operations Research
12 European Journal of Combinatorics
12 Journal of Machine Learning Research (JMLR)
12 Discrete Mathematics, Algorithms and Applications
11 Artificial Intelligence
11 Journal of Combinatorial Theory. Series B
10 Random Structures & Algorithms
10 ACM Journal of Experimental Algorithmics
9 International Journal of Computational Geometry & Applications
9 Journal of Global Optimization
9 Combinatorics, Probability and Computing
9 The Electronic Journal of Combinatorics
8 Networks
8 Games and Economic Behavior
8 Mathematics in Computer Science
8 Optimization Letters
7 Operations Research
7 Graphs and Combinatorics
7 Linear Algebra and its Applications
7 SIAM Journal on Optimization
7 Journal of the ACM
6 Acta Informatica
6 Computing
6 Journal of Symbolic Computation
6 INFORMS Journal on Computing
6 Computer Science Review
5 Mathematical Social Sciences
5 Journal of Cryptology
5 Journal of Parallel and Distributed Computing
5 Data Mining and Knowledge Discovery
5 ACM Transactions on Algorithms
4 Mathematics of Computation
4 Applied Mathematics and Computation
4 Journal of Combinatorial Theory. Series A
4 Combinatorica
4 Social Choice and Welfare
4 Machine Learning
4 Designs, Codes and Cryptography
4 International Journal of Computer Mathematics
4 Computational Complexity
4 Computational Optimization and Applications
4 SIAM Journal on Scientific Computing
4 Annals of Mathematics and Artificial Intelligence
4 Constraints
4 International Journal of Applied Mathematics and Computer Science
4 Foundations of Computational Mathematics
4 Internet Mathematics
4 Journal of the Operations Research Society of China
4 Electronic Journal of Graph Theory and Applications
3 Journal of Computational Physics
3 Journal of Mathematical Biology
3 ACM Transactions on Database Systems
3 Journal of Graph Theory
3 Journal of Mathematical Economics
3 Advances in Applied Mathematics
3 Asia-Pacific Journal of Operational Research
3 MSCS. Mathematical Structures in Computer Science
3 Cybernetics and Systems Analysis
3 Top
3 The Journal of Artificial Intelligence Research (JAIR)
3 Bernoulli
3 Philosophical Transactions of the Royal Society of London. Series A. Mathematical, Physical and Engineering Sciences
3 RAIRO. Operations Research
3 Proceedings of the Steklov Institute of Mathematics
3 Prikladnaya Diskretnaya Matematika
2 Computers & Mathematics with Applications
2 International Journal of Game Theory
2 Journal of Applied Probability
2 Journal of Economic Theory
2 Journal of Optimization Theory and Applications
2 Programming and Computer Software
2 Circuits, Systems, and Signal Processing
2 Computer Aided Geometric Design
2 Acta Mathematicae Applicatae Sinica. English Series
...and 128 more Journals
all top 5

Cited in 44 Fields

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

Citations by Year