×

Theory of Computing Systems

Short Title: Theory Comput. Syst.
Publisher: Springer US, New York, NY
ISSN: 1432-4350; 1433-0490/e
Online: https://link.springer.com/journal/224/volumes-and-issues
Predecessor: Mathematical Systems Theory
Comments: Journal; Indexed cover-to-cover
Documents Indexed: 1,506 Publications (since 1997)
References Indexed: 1,054 Publications with 27,202 References.
all top 5

Latest Issues

68, No. 2 (2024)
68, No. 1 (2024)
67, No. 6 (2023)
67, No. 5 (2023)
67, No. 4 (2023)
67, No. 3 (2023)
67, No. 2 (2023)
67, No. 1 (2023)
66, No. 6 (2022)
66, No. 5 (2022)
66, No. 4 (2022)
66, No. 3 (2022)
66, No. 2 (2022)
66, No. 1 (2022)
65, No. 8 (2021)
65, No. 7 (2021)
65, No. 6 (2021)
65, No. 5 (2021)
65, No. 4 (2021)
65, No. 3 (2021)
65, No. 2 (2021)
65, No. 1 (2021)
64, No. 8 (2020)
64, No. 7 (2020)
64, No. 6 (2020)
64, No. 5 (2020)
64, No. 4 (2020)
64, No. 3 (2020)
64, No. 2 (2020)
64, No. 1 (2020)
63, No. 8 (2019)
63, No. 7 (2019)
63, No. 6 (2019)
63, No. 5 (2019)
63, No. 4 (2019)
63, No. 3 (2019)
63, No. 2 (2019)
63, No. 1 (2019)
62, No. 8 (2018)
62, No. 7 (2018)
62, No. 6 (2018)
62, No. 5 (2018)
62, No. 4 (2018)
62, No. 3 (2018)
62, No. 2 (2018)
62, No. 1 (2018)
61, No. 4 (2017)
61, No. 3 (2017)
61, No. 2 (2017)
61, No. 1 (2017)
60, No. 4 (2017)
60, No. 3 (2017)
60, No. 2 (2017)
60, No. 1 (2017)
59, No. 4 (2016)
59, No. 3 (2016)
59, No. 2 (2016)
59, No. 1 (2016)
58, No. 4 (2016)
58, No. 3 (2016)
58, No. 2 (2016)
58, No. 1 (2016)
57, No. 4 (2015)
57, No. 3 (2015)
57, No. 2 (2015)
57, No. 1 (2015)
56, No. 4 (2015)
56, No. 3 (2015)
56, No. 2 (2015)
56, No. 1 (2015)
55, No. 4 (2014)
55, No. 3 (2014)
55, No. 2 (2014)
55, No. 1 (2014)
54, No. 4 (2014)
54, No. 3 (2014)
54, No. 2 (2014)
54, No. 1 (2014)
53, No. 4 (2013)
53, No. 3 (2013)
53, No. 2 (2013)
53, No. 1 (2013)
52, No. 4 (2013)
52, No. 3 (2013)
52, No. 2 (2013)
52, No. 1 (2013)
51, No. 4 (2012)
51, No. 3 (2012)
51, No. 2 (2012)
51, No. 1 (2012)
50, No. 4 (2012)
50, No. 3 (2012)
50, No. 2 (2012)
50, No. 1 (2012)
49, No. 4 (2011)
49, No. 3 (2011)
49, No. 2 (2011)
49, No. 1 (2011)
48, No. 4 (2011)
48, No. 3 (2011)
...and 90 more Volumes
all top 5

Authors

15 Spirakis, Paul G.
12 Fotakis, Dimitris A.
12 Lohrey, Markus
11 Mayordomo, Elvira
11 Saurabh, Saket
11 Scheideler, Christian
10 Cai, Jin-Yi
10 Diekert, Volker
10 Niedermeier, Rolf
9 Anshelevich, Elliot
9 Caragiannis, Ioannis
9 Fomin, Fedor V.
9 Kaklamanis, Christos
9 Patt-Shamir, Boaz
8 Bilò, Vittorio
8 Bodlaender, Hans L.
8 Bollig, Beate
8 Buhrman, Harry
8 Epstein, Leah
8 Golovach, Petr A.
8 Hitchcock, John M.
8 Mavronicolas, Marios
8 Meyer auf der Heide, Friedhelm
8 Ogihara, Mitsunori
7 Allender, Eric W.
7 Bergstra, Jan A.
7 Carton, Olivier
7 Krizanc, Danny
7 Luccio, Fabrizio
7 Lutz, Jack H.
7 Merkle, Wolfgang
7 Monien, Burkhard
7 Raman, Venkatesh
7 Shen, Alexander
7 Thérien, Denis
7 Vogler, Heiko
7 Watanabe, Osamu
6 Bauwens, Bruno
6 Bender, Michael A.
6 Dürr, Christoph
6 Fellows, Michael Ralph
6 Flammini, Michele
6 Fraigniaud, Pierre
6 Jeż, Artur
6 Kufleitner, Manfred
6 Luccio, Flaminia L.
6 McNicholl, Timothy H.
6 Okhotin, Alexander
6 Rosenberg, Arnold Leonard
6 Rothe, Jörg-Matthias
6 Schwentick, Thomas
6 Vereshchagin, Nikolay K.
6 Vollmer, Heribert
5 Antunes, Luis
5 Azar, Yossi
5 Bienvenu, Laurent
5 Blelloch, Guy E.
5 Cygan, Marek
5 Dehne, Frank
5 Erlebach, Thomas
5 Fortnow, Lance J.
5 Fülöp, Zoltán
5 Gibbons, Phillip B.
5 Grädel, Erich
5 Hansen, Kristoffer Arnsfelt
5 Langerman, Stefan
5 Litman, Ami
5 Mahajan, Meena
5 Markakis, Evangelos
5 Muscholl, Anca
5 Nikoletseas, Sotiris E.
5 Pavan, Aduri
5 Persiano, Giuseppe
5 Pilipczuk, Marcin L.
5 Pucci, Geppino
5 Rosamond, Frances A.
5 Rossmanith, Peter
5 Serna Iglesias, Maria José
5 Stephan, Frank
4 Albers, Susanne
4 Arvind, Vikraman
4 Asano, Tetsuo
4 Barceló, Pablo
4 Bille, Philip
4 Bläser, Markus
4 Brandt, Felix
4 Cenzer, Douglas
4 Christodoulou, George C.
4 Demaine, Erik D.
4 Downey, Rodney Graham
4 Droste, Manfred
4 Durand, Arnaud
4 Fanelli, Angelo
4 Fernau, Henning
4 Fischer, Felix
4 Flocchini, Paola
4 Freydenberger, Dominik D.
4 Geerts, Floris
4 Guo, Jiong
4 Gurski, Frank
...and 2,311 more Authors

Publications by Year

Citations contained in zbMATH Open

1,058 Publications have been cited 7,378 times in 6,097 Documents Cited by Year
Linear time solvable optimization problems on graphs of bounded clique-width. Zbl 1009.68102
Courcelle, B.; Makowsky, J. A.; Rotics, U.
411
2000
Polynomial closure and unambiguous product. Zbl 0872.68119
Pin, J.-E.; Weil, P.
74
1997
Compressed suffix trees with full functionality. Zbl 1148.68015
Sadakane, Kunihiko
68
2007
Graph-modeled data clustering: Exact algorithms for clique generation. Zbl 1084.68117
Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf
61
2005
Upper and lower bounds for randomized search heuristics in black-box optimization. Zbl 1103.68115
Droste, Stefan; Jansen, Thomas; Wegener, Ingo
61
2006
On covering problems of codes. Zbl 0868.94056
Frances, M.; Litman, A.
59
1997
Generating shorter bases for hard random lattices. Zbl 1217.94092
Alwen, Joël; Peikert, Chris
56
2011
On short paths interdiction problems: Total and node-wise limited interdiction. Zbl 1148.68036
Boros, Endre; Borys, Konrad; Elbassioni, Khaled; Gurvich, Vladimir; Rudolf, Gabor; Zhao, Jihui
54
2008
Finite presentations of infinite structures: Automata and interpretations. Zbl 1061.03038
Blumensath, Achim; Grädel, Erich
52
2004
Fixed-parameter algorithms for cluster vertex deletion. Zbl 1205.68263
Hüffner, Falk; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf
50
2010
Fixed points, Nash equilibria, and the existential theory of the reals. Zbl 1362.68088
Schaefer, Marcus; Štefankovič, Daniel
46
2017
Network design with weighted players. Zbl 1176.91003
Chen, Ho-Lin; Roughgarden, Tim
45
2009
Crown structures for vertex cover kernelization. Zbl 1148.68035
Abu-Khzam, Faisal N.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry
43
2007
Approximate equilibria and ball fusion. Zbl 1101.68336
Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul
42
2003
Parameterized complexity of Vertex Cover variants. Zbl 1147.68607
Guo, Jiong; Niedermeier, Rolf; Wernicke, Sebastian
41
2007
Balanced graph partitioning. Zbl 1113.68069
Andreev, Konstantin; Räcke, Harald
41
2006
Numeration systems on a regular language. Zbl 0969.68095
Lecomte, P. B. A.; Rigo, M.
40
2001
Clique-width for 4-vertex forbidden subgraphs. Zbl 1103.68088
Brandstädt, Andreas; Engelfriet, Joost; Le, Hoang-Oanh; Lozin, Vadim V.
38
2006
On edge irregular total labeling of categorical product of two cycles. Zbl 1284.05232
Ahmad, Ali; Bača, Martin; Siddiqui, Muhammad Kamran
38
2014
Applying modular decomposition to parameterized cluster editing problems. Zbl 1179.68111
Protti, Fábio; Dantas da Silva, Maise; Szwarcfiter, Jayme Luiz
37
2009
Nearest common ancestors: a survey and a new algorithm for a distributed environment. Zbl 1093.68136
Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis
35
2004
The efficiency of fair division. Zbl 1262.91099
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria
35
2012
A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
34
2016
Undecidable problems for probabilistic automata of fixed dimension. Zbl 1039.68061
Blondel, Vincent D.; Canterini, Vincent
33
2003
Exact complexity of the winner problem for Young elections. Zbl 1061.90084
Rothe, Jörg; Spakowski, Holger; Vogel, Jörg
31
2003
A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Zbl 0896.68080
Staiger, L.
31
1998
Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter. Zbl 1286.68196
Jansen, Bart M. P.; Bodlaender, Hans L.
31
2013
The complexity ecology of parameters: An illustration using bounded max leaf number. Zbl 1184.05123
Fellows, Michael; Lokshtanov, Daniel; Misra, Neeldhara; Mnich, Matthias; Rosamond, Frances; Saurabh, Saket
30
2009
Algebraic results on quantum automata. Zbl 1101.68029
Ambainis, Andris; Beaudry, Martin; Golovkins, Marats; Kikusts, Arnolds; Mercer, Mark; Therien, Denis
30
2006
Constant thresholds can make target set selection tractable. Zbl 1319.68109
Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias
30
2014
Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Zbl 1148.68041
Mölle, Daniel; Richter, Stefan; Rossmanith, Peter
29
2008
Complexity of Presburger arithmetic with fixed quantifier dimension. Zbl 0872.68048
Schöning, U.
29
1997
Accessing nearby copies of replicated objects in a distributed environment. Zbl 0929.68126
Plaxton, C. G.; Rajaraman, R.; Richa, A. W.
29
1999
Irregular total labellings of generalized Petersen graphs. Zbl 1254.05172
Haque, Khandoker Mohammed Mominul
29
2012
Equational elements in additive algebras. Zbl 0914.68118
Bozapalidis, S.
27
1999
The complexity of equality constraint languages. Zbl 1148.68025
Bodirsky, Manuel; Kára, Jan
26
2008
First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Zbl 0904.68137
Muthukrishnan, S.; Ghosh, B.; Schultz, M. H.
26
1998
On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109
Berman, P.; Fujito, T.
26
1999
Nash equilibria and the price of anarchy for flows over time. Zbl 1278.91027
Koch, Ronald; Skutella, Martin
26
2011
An \(\mathcal O(2^{O(k)}n^{3})\) FPT algorithm for the undirected feedback vertex set problem. Zbl 1148.68037
Dehne, Frank; Fellows, Michael; Langston, Michael; Rosamond, Frances; Stevens, Kim
25
2007
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327
Jeż, Artur; Okhotin, Alexander
25
2010
Local MST computation with short advice. Zbl 1213.68123
Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle
25
2010
New graph classes of bounded clique-width. Zbl 1084.68088
Brandstädt, Andreas; Dragan, Feodor F.; Le, Hoàng-Oanh; Mosca, Raffaele
25
2005
Space efficient hash tables with worst case constant access time. Zbl 1066.68025
Fotakis, Dimitris; Pagh, Rasmus; Sanders, Peter; Spirakis, Paul
25
2005
The linear arrangement problem parameterized above guaranteed value. Zbl 1148.68039
Gutin, Gregory; Rafiey, Arash; Szeider, Stefan; Yeo, Anders
24
2007
Dynamic programming for minimum Steiner trees. Zbl 1148.68038
Fuchs, B.; Kern, W.; Molle, D.; Richter, S.; Rossmanith, P.; Wang, X.
24
2007
The power of commuting with finite sets of words. Zbl 1121.68065
Kunc, Michal
24
2007
A cubic kernel for feedback vertex set and loop cutset. Zbl 1215.68170
Bodlaender, Hans L.; van Dijk, Thomas C.
24
2010
Correspondence principles for effective dimensions. Zbl 1084.68054
Hitchcock, John M.
24
2005
Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. Zbl 1179.68055
Gradwohl, Ronen; Naor, Moni; Pinkas, Benny; Rothblum, Guy N.
24
2009
A generalization of Cobham’s theorem. Zbl 0895.68081
Durand, F.
24
1998
\(\frac{13}{9}\)-approximation for graphic TSP. Zbl 1319.68255
Mucha, Marcin
24
2014
The complexity of optimal design of temporally connected graphs. Zbl 1379.68250
Akrida, Eleni C.; Gąsieniec, Leszek; Mertzios, George B.; Spirakis, Paul G.
23
2017
Quotient complexity of closed languages. Zbl 1380.68249
Brzozowski, Janusz; Jirásková, Galina; Zou, Chenglong
23
2014
The hub number of Sierpiński-like graphs. Zbl 1234.05178
Lin, Chien-Hung; Liu, Jia-Jie; Wang, Yue-Li; Yen, William Chung-Kung
23
2011
Simple and improved parameterized algorithms for multiterminal cuts. Zbl 1213.68472
Xiao, Mingyu
22
2010
Efficient exact algorithms through enumerating maximal independent sets and other techniques. Zbl 1148.68054
Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath
22
2007
Randomness on computable probability spaces – a dynamical point of view. Zbl 1238.68069
Gács, Peter; Hoyrup, Mathieu; Rojas, Cristóbal
22
2011
Stackelberg strategies for atomic congestion games. Zbl 1203.91035
Fotakis, Dimitris
22
2010
From a zoo to a zoology: Towards a general theory of graph polynomials. Zbl 1162.68502
Makowsky, J. A.
22
2008
Sofic tree-shifts. Zbl 1293.68195
Aubrun, Nathalie; Béal, Marie-Pierre
21
2013
How to prove impossibility under global fairness: on space complexity of self-stabilizing leader election on a population protocol model. Zbl 1281.68049
Cai, Shukai; Izumi, Taisuke; Wada, Koichi
21
2012
On approximate jumbled pattern matching in strings. Zbl 1253.68372
Burcsi, Péter; Cicalese, Ferdinando; Fici, Gabriele; Lipták, Zsuzsanna
21
2012
Real hypercomputation and continuity. Zbl 1122.03039
Ziegler, Martin
20
2007
Vertex cover problem parameterized above and below tight bounds. Zbl 1209.68276
Gutin, Gregory; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia
20
2011
Distributed streams algorithms for sliding windows. Zbl 1093.68143
Gibbons, Phillip B.; Tirthapura, Srikanta
20
2004
Regular languages and Stone duality. Zbl 0870.68092
Pippenger, N.
20
1997
Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Zbl 1380.68257
Martyugin, Pavel
20
2014
The behavior of clique-width under graph operations and graph transformations. Zbl 1358.05239
Gurski, Frank
20
2017
A note on exact algorithms for vertex ordering problems on graphs. Zbl 1253.68164
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M.
20
2012
Weak MSO with the unbounding quantifier. Zbl 1227.03051
Bojańczyk, Mikołaj
19
2011
Efficient update strategies for geometric computing with uncertainty. Zbl 1084.68131
Bruce, Richard; Hoffmann, Michael; Krizanc, Danny; Raman, Rajeev
19
2005
Solving the 2-disjoint paths problem in nearly linear time. Zbl 1103.68100
Tholey, Torsten
19
2006
Descendants of primitive substitutions. Zbl 0916.68086
Holton, C.; Zamboni, L. Q.
19
1999
Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022
Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola
18
2007
DNA computing based on splicing: The existence of universal computers. Zbl 0914.68072
Freund, R.; Kari, L.; Păun, Gh.
18
1999
The price of anarchy in network creation games is (mostly) constant. Zbl 1293.91031
Mihalák, Matúš; Schlegel, Jan Christoph
18
2013
Characterizing the existence of potential functions in weighted congestion games. Zbl 1278.91013
Harks, Tobias; Klimm, Max; Möhring, Rolf H.
18
2011
The rank-width of edge-coloured graphs. Zbl 1269.05036
Kanté, Mamadou Moustapha; Rao, Michael
18
2013
The hardness of approximating spanner problems. Zbl 1148.68024
Elkin, Michael; Peleg, David
17
2007
Robust polynomials and quantum algorithms. Zbl 1121.68049
Buhrman, Harry; Newman, Ilan; Rohrig, Hein; de Wolf, Ronald
17
2007
Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications. Zbl 1175.90366
Tsaggouris, George; Zaroliagis, Christos
17
2009
Planar and grid graph reachability problems. Zbl 1183.68409
Allender, Eric; Mix Barrington, David A.; Chakraborty, Tanmoy; Datta, Samir; Roy, Sambuddha
17
2009
Thread scheduling for multiprogrammed multiprocessors. Zbl 0978.68020
Arora, N. S.; Blumofe, R. D.; Plaxton, C. G.
17
2001
A Kleene theorem for weighted tree automata. Zbl 1061.68092
Droste, Manfred; Pech, Christian; Vogler, Heiko
17
2005
On the uniform computational content of computability theory. Zbl 1420.03110
Brattka, Vasco; Hendtlass, Matthew; Kreuzer, Alexander P.
17
2017
The bell is ringing in speed-scaled multiprocessor scheduling. Zbl 1310.68048
Greiner, Gero; Nonner, Tim; Souza, Alexander
17
2014
Gaming is a hard job, but someone has to do it! Zbl 1303.68075
Viglietta, Giovanni
17
2014
Fixed-parameter enumerability of cluster editing and related problems. Zbl 1209.68360
Damaschke, Peter
16
2010
Selfish routing with incomplete information. Zbl 1151.91331
Gairing, Martin; Monien, Burkhard; Tiemann, Karsten
16
2008
Weighted logics for unranked tree automata. Zbl 1226.03048
Droste, Manfred; Vogler, Heiko
16
2011
Complexity of equations over sets of natural numbers. Zbl 1209.68263
Jeż, Artur; Okhotin, Alexander
16
2011
Weighted picture automata and weighted logics. Zbl 1229.03035
Fichtner, Ina
16
2011
Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs. Zbl 1170.90461
Athanassopoulos, Stavros; Caragiannis, Ioannis; Kaklamanis, Christos
16
2009
Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults. Zbl 1187.68344
Hsieh, Sun-Yuan; Weng, Yu-Fen
16
2009
Greedy numeration systems and regularity. Zbl 0895.68088
Hollander, Michael Israel
16
1998
Local approximability of max-min and min-max linear programs. Zbl 1253.68360
Floréen, Patrik; Hassinen, Marja; Kaasinen, Joel; Kaski, Petteri; Musto, Topi; Suomela, Jukka
16
2011
Symbolic dynamics: entropy = dimension = complexity. Zbl 1355.37023
Simpson, Stephen G.
16
2015
The parameterized approximability of TSP with deadlines. Zbl 1148.68052
Böckenhauer, Hans-Joachim; Hromkovič, Juraj; Kneis, Joachim; Kupke, Joachim
15
2007
Lower bounds for kernelizations and other preprocessing procedures. Zbl 1234.68118
Chen, Yijia; Flum, Jörg; Müller, Moritz
15
2011
Solving vertex cover in polynomial time on hyperbolic random graphs. Zbl 1512.05356
Bläsius, Thomas; Fischbeck, Philipp; Friedrich, Tobias; Katzmann, Maximilian
2
2023
Decidability and periodicity of low complexity tilings. Zbl 07680321
Kari, Jarkko; Moutot, Etienne
2
2023
An automaton group with PSPACE-complete word problem. Zbl 07680323
Wächter, Jan Philipp; Weiß, Armin
1
2023
Random access in persistent strings and segment selection. Zbl 07729114
Bille, Philip; Gørtz, Inge Li
1
2023
Dynamic multiple-message broadcast: bounding throughput in the affectance model. Zbl 07729119
Kowalski, Dariusz R.; Mosteiro, Miguel A.; Zaki, Kevin
1
2023
Subclasses of Ptime interpreted by programming languages. Zbl 07719393
Bhaskar, Siddharth; Kop, Cynthia; Simonsen, Jakob Grue
1
2023
The space complexity of sum labelling. Zbl 1533.05233
Fernau, Henning; Gajjar, Kshitij
1
2023
FKT is not universal – a planar Holant dichotomy for symmetric constraints. Zbl 1534.68075
Cai, Jin-Yi; Fu, Zhiguo; Guo, Heng; Williams, Tyson
7
2022
Multistage vertex cover. Zbl 07523542
Fluschnik, Till; Niedermeier, Rolf; Rohm, Valentin; Zschoche, Philipp
4
2022
An improved deterministic parameterized algorithm for cactus vertex deletion. Zbl 1487.05250
Aoike, Yuuki; Gima, Tatsuya; Hanaka, Tesshu; Kiyomi, Masashi; Kobayashi, Yasuaki; Kobayashi, Yusuke; Kurita, Kazuhiro; Otachi, Yota
4
2022
On the computational complexity of decision problems about multi-player Nash equilibria. Zbl 1493.91005
Berthelsen, Marie Louisa Tølbøll; Hansen, Kristoffer Arnsfelt
4
2022
On the existence of three-dimensional stable matchings with cyclic preferences. Zbl 1493.91093
Lam, Chi-Kit; Plaxton, C. Gregory
2
2022
Stable multi-level monotonic eroders. Zbl 1536.37019
Gács, Péter; Törmä, Ilkka
1
2022
Multi-pass streaming algorithms for monotone submodular function maximization. Zbl 1533.68414
Huang, Chien-Chung; Kakimura, Naonori
1
2022
The power of the weighted sum scalarization for approximating multiobjective optimization problems. Zbl 1485.90121
Bazgan, Cristina; Ruzika, Stefan; Thielen, Clemens; Vanderpooten, Daniel
1
2022
The declining price anomaly is not universal in multi-buyer sequential auctions (but almost is). Zbl 1493.91058
Narayan, Vishnu V.; Prebet, Enguerrand; Vetta, Adrian
1
2022
Maximum stable matching with one-sided ties of bounded length. Zbl 1489.68401
Lam, Chi-Kit; Plaxton, C. Gregory
1
2022
Impartial selection with additive approximation guarantees. Zbl 1493.91029
Caragiannis, Ioannis; Christodoulou, George; Protopapas, Nicos
1
2022
Non-existence of stable social groups in information-driven networks. Zbl 1495.91088
Chaintreau, Augustin; Ducoffe, Guillaume; Mazauric, Dorian
1
2022
Faster parameterized algorithm for cluster vertex deletion. Zbl 1517.68308
Tsur, Dekel
11
2021
Token sliding on split graphs. Zbl 1517.68273
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian
10
2021
Computability of products of chainable continua. Zbl 1535.03228
Čelar, Matea; Iljazović, Zvonko
6
2021
Finite sequentiality of unambiguous max-plus tree automata. Zbl 1517.68211
Paul, Erik
5
2021
The containment problem for unambiguous register automata and unambiguous timed automata. Zbl 1517.68207
Mottet, Antoine; Quaas, Karin
4
2021
Approximation results for makespan minimization with budgeted uncertainty. Zbl 1478.90036
Bougeret, Marin; Jansen, Klaus; Poss, Michael; Rohwedder, Lars
4
2021
The price of fairness for indivisible goods. Zbl 1471.91196
Bei, Xiaohui; Lu, Xinhang; Manurangsi, Pasin; Suksompong, Warut
4
2021
Fast scheduling in distributed transactional memory. Zbl 1464.68036
Busch, Costas; Herlihy, Maurice; Popovic, Miroslav; Sharma, Gokarna
4
2021
On triangle estimation using tripartite independent set queries. Zbl 1508.68259
Bhattacharya, Anup; Bishnu, Arijit; Ghosh, Arijit; Mishra, Gopinath
4
2021
Unpopularity factor in the marriage and roommates problems. Zbl 1518.91175
Ruangwises, Suthee; Itoh, Toshiya
3
2021
On the cycle augmentation problem: hardness and approximation algorithms. Zbl 1473.05292
Gálvez, Waldo; Grandoni, Fabrizio; Jabal Ameli, Afrouz; Sornat, Krzysztof
3
2021
Parameterized complexity of conflict-free set cover. Zbl 1517.68146
Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh
2
2021
The non-hardness of approximating circuit size. Zbl 1522.68194
Allender, Eric; Ilango, Rahul; Vafa, Neekon
2
2021
Forward looking Huffman coding. Zbl 1517.68111
Klein, Shmuel T.; Saadia, Shoham; Shapira, Dana
2
2021
First-order orbit queries. Zbl 1518.37014
Almagor, Shaull; Ouaknine, Joël; Worrell, James
2
2021
Streaming algorithms for bin packing and vector scheduling. Zbl 1528.68408
Cormode, Graham; Veselý, Pavel
2
2021
Semi-oblivious chase termination: the sticky case. Zbl 1477.68088
Calautti, Marco; Pieris, Andreas
2
2021
Restart strategies in a continuous setting. Zbl 1508.68413
Lorenz, Jan-Hendrik
2
2021
A parameterized complexity view on collapsing \(k\)-cores. Zbl 1508.68269
Luo, Junjie; Molter, Hendrik; Suchý, Ondřej
2
2021
Transition property for cube-free words. Zbl 1517.68322
Petrova, Elena A.; Shur, Arseny M.
1
2021
On Tseitin formulas, read-once branching programs and treewidth. Zbl 1517.68092
Glinskih, Ludmila; Itsykson, Dmitry
1
2021
Constructing antidictionaries of long texts in output-sensitive space. Zbl 1517.68428
Ayad, Lorraine A. K.; Badkobeh, Golnaz; Fici, Gabriele; Héliou, Alice; Pissis, Solon P.
1
2021
The minimum tollbooth problem in atomic network congestion games with unsplittable flows. Zbl 1471.91020
Nickerl, Julian
1
2021
Index-based, high-dimensional, cosine threshold querying with optimality guarantees. Zbl 1517.68101
Li, Yuliang; Wang, Jianguo; Pullman, Benjamin; Bandeira, Nuno; Papakonstantinou, Yannis
1
2021
Consistent query answering for primary keys in Datalog. Zbl 1477.68091
Koutris, Paraschos; Wijsen, Jef
1
2021
On the expressive power of linear algebra on graphs. Zbl 1466.05118
Geerts, Floris
1
2021
Stable divisorial gonality is in NP. Zbl 1477.68204
Bodlaender, Hans L.; van der Wegen, Marieke; van der Zanden, Tom C.
1
2021
On the relation between structured \(d\)-DNNFs and SDDs. Zbl 1522.68536
Bollig, Beate; Farenholtz, Martin
1
2021
Reachability problems on reliable and lossy queue automata. Zbl 1503.68174
Köcher, Chris
1
2021
Additive number theory via automata theory. Zbl 1475.11040
Rajasekaran, Aayush; Shallit, Jeffrey; Smith, Tim
11
2020
Complexity and inapproximability results for parallel task scheduling and strip packing. Zbl 1477.68119
Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars
6
2020
On the tree conjecture for the network creation game. Zbl 1443.91071
Bilò, Davide; Lenzner, Pascal
6
2020
Optimal dislocation with persistent errors in subquadratic time. Zbl 1433.68111
Geissmann, Barbara; Leucci, Stefano; Liu, Chih-Hung; Penna, Paolo
5
2020
On the parameterized complexity of graph modification to first-order logic properties. Zbl 1434.68208
Fomin, Fedor V.; Golovach, Petr A.; Thilikos, Dimitrios M.
4
2020
Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits. Zbl 1433.68177
Bannach, Max; Tantau, Till
4
2020
Conflict free version of covering problems on graphs: classical and parameterized. Zbl 1453.68136
Jain, Pallavi; Kanesh, Lawqueen; Misra, Pranabendu
4
2020
Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings. Zbl 1503.68317
Watanabe, Kiichi; Nakashima, Yuto; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki
4
2020
Lower bound techniques for QBF expansion. Zbl 1471.03081
Beyersdorff, Olaf; Blinkhorn, Joshua
3
2020
Dependences in strategy logic. Zbl 1484.68100
Gardy, Patrick; Bouyer, Patricia; Markey, Nicolas
3
2020
Parameterized complexity of min-power asymmetric connectivity. Zbl 1503.68080
Bentert, Matthias; Haag, Roman; Hofer, Christian; Koana, Tomohiro; Nichterlein, André
3
2020
On limitations of structured (deterministic) DNNFs. Zbl 1446.68152
Bollig, Beate; Buttkus, Matthias
2
2020
Enumeration complexity of conjunctive queries with functional dependencies. Zbl 1446.68052
Carmeli, Nofar; Kröll, Markus
2
2020
Connecting knowledge compilation classes and width parameters. (Connecting knowledge compilation classes width parameters.) Zbl 1446.68149
Amarilli, Antoine; Capelli, Florent; Monet, Mikaël; Senellart, Pierre
2
2020
An improved FPT algorithm for independent feedback vertex set. Zbl 1507.68231
Li, Shaohua; Pilipczuk, Marcin
2
2020
Multiplication algorithm based on Collatz function. Zbl 1462.11112
Barina, David
2
2020
Dichotomy for Holant\(^\ast\) problems on the Boolean domain. Zbl 1503.68199
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
2
2020
Advice complexity of priority algorithms. Zbl 1444.68299
Borodin, Allan; Boyar, Joan; Larsen, Kim S.; Pankratov, Denis
1
2020
Recognizing read-once functions from depth-three formulas. Zbl 1434.68201
Kozachinskiy, Alexander
1
2020
Slopes of multidimensional subshifts. Zbl 1440.37025
Jeandel, Emmanuel; Moutot, Etienne; Vanier, Pascal
1
2020
Fixed-parameter tractable algorithm and polynomial kernel for Max-Cut Above Spanning Tree. Zbl 1434.68748
Madathil, Jayakrishnan; Saurabh, Saket; Zehavi, Meirav
1
2020
New bounds for truthful scheduling on two unrelated selfish machines. Zbl 1434.68678
Kuryatnikova, Olga; Vera, Juan C.
1
2020
On approximating the stationary distribution of time-reversible Markov chains. Zbl 1436.60035
Bressan, Marco; Peserico, Enoch; Pretto, Luca
1
2020
Deterministic min-cost matching with delays. Zbl 1444.68297
Azar, Yossi; Jacob Fanani, Amit
1
2020
Effective categoricity of automatic equivalence and nested equivalence structures. Zbl 1485.03109
Carson, Jacob; Cenzer, Douglas; Remmel, Jeffrey B.
1
2020
Santha-Vazirani sources, deterministic condensers and very strong extractors. Zbl 1476.68081
Gavinsky, Dmitry; Pudlák, Pavel
1
2020
On the stab number of rectangle intersection graphs. Zbl 1442.05187
Chakraborty, Dibyayan; Francis, Mathew C.
1
2020
Complexity of fall coloring for restricted graph classes. Zbl 1507.68230
Lauri, Juho; Mitillos, Christodoulos
1
2020
Complexity and algorithms for semipaired domination in graphs. Zbl 1503.68223
Henning, Michael A.; Pandey, Arti; Tripathi, Vikash
1
2020
On envy-free revenue approximation for combinatorial buyers with budgets. Zbl 1466.91121
Markakis, Evangelos; Ntokos, Apostolos; Telelis, Orestis
1
2020
Distribution policies for Datalog. Zbl 1446.68057
Ketsman, Bas; Albarghouthi, Aws; Koutris, Paraschos
1
2020
Generic results for concatenation hierarchies. Zbl 1423.68264
Place, Thomas; Zeitoun, Marc
12
2019
Verification of quantum computation: an overview of existing approaches. Zbl 1423.68281
Gheorghiu, Alexandru; Kapourniotis, Theodoros; Kashefi, Elham
11
2019
Lower bounds for several online variants of bin packing. Zbl 1436.68402
Balogh, János; Békési, József; Dósa, György; Epstein, Leah; Levin, Asaf
8
2019
On the parameterized complexity of contraction to generalization of trees. Zbl 1435.68119
Agarwal, Akanksha; Saurabh, Saket; Tale, Prafullkumar
8
2019
On the relative succinctness of sentential decision diagrams. Zbl 1435.68320
Bollig, Beate; Buttkus, Matthias
7
2019
Comparing linear width parameters for directed graphs. Zbl 1420.05068
Gurski, Frank; Rehs, Carolin
6
2019
The real computational complexity of minmax value and equilibrium refinements in multi-player games. Zbl 1422.91046
Hansen, Kristoffer Arnsfelt
6
2019
A logic for document spanners. Zbl 1430.68081
Freydenberger, Dominik D.
6
2019
The operator approach to entropy games. Zbl 1422.91080
Akian, Marianne; Gaubert, Stéphane; Grand-Clément, Julien; Guillaud, Jérémie
5
2019
Logarithmic query complexity for approximate Nash computation in large games. Zbl 1411.91052
Goldberg, Paul W.; Marmolejo-Cossío, Francisco J.; Wu, Zhiwei Steven
5
2019
Synchronous gathering without multiplicity detection: a certified algorithm. Zbl 1423.68522
Balabonski, Thibaut; Delga, Amélie; Rieg, Lionel; Tixeuil, Sébastien; Urbain, Xavier
4
2019
Pattern matching and consensus problems on weighted sequences and profiles. Zbl 1423.68620
Kociumaka, Tomasz; Pissis, Solon P.; Radoszewski, Jakub
4
2019
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68114
Verbitsky, Oleg; Zhukovskii, Maksim
4
2019
Better streaming algorithms for the maximum coverage problem. Zbl 1421.90128
McGregor, Andrew; Vu, Hoa T.
4
2019
The stable roommates problem with short lists. Zbl 1418.91387
Cseh, Ágnes; Irving, Robert W.; Manlove, David F.
3
2019
The conjugacy problem in free solvable groups and wreath products of abelian groups is in \(\mathsf{TC}^0\). Zbl 1453.20045
Miasnikov, Alexei; Vassileva, Svetla; Weiß, Armin
3
2019
On Stackelberg strategies in affine congestion games. Zbl 1422.91143
Bilò, Vittorio; Vinci, Cosimo
3
2019
A group algebraic approach to NPN classification of Boolean functions. Zbl 1462.94074
Zhang, Juling; Yang, Guowu; Hung, William N. N.; Liu, Tian; Song, Xiaoyu; Perkowski, Marek A.
3
2019
Bounds on the bend number of split and cocomparability graphs. Zbl 1420.05120
Chakraborty, Dibyayan; Das, Sandip; Mukherjee, Joydeep; Sahoo, Uma Kant
3
2019
Price of anarchy for highly congested routing games in parallel networks. Zbl 1411.91136
Colini-Baldeschi, Riccardo; Cominetti, Roberto; Scarsini, Marco
3
2019
On conceptually simple algorithms for variants of online bipartite matching. Zbl 1429.91230
Borodin, Allan; Pankratov, Denis; Salehi-Abari, Amirali
2
2019
...and 958 more Documents
all top 5

Cited by 7,271 Authors

69 Saurabh, Saket
50 Niedermeier, Rolf
47 Fomin, Fedor V.
46 Paulusma, Daniël
41 Golovach, Petr A.
33 Epstein, Leah
33 Lohrey, Markus
32 Lozin, Vadim Vladislavovich
32 Okhotin, Alexander
31 Ganian, Robert
30 Lokshtanov, Daniel
30 Stephan, Frank
28 Bilò, Vittorio
27 Courcelle, Bruno
27 Jansen, Bart M. P.
27 Spirakis, Paul G.
26 Dabrowski, Konrad Kazimierz
26 Mavronicolas, Marios
25 Fellows, Michael Ralph
25 Fernau, Henning
25 Komusiewicz, Christian
25 Rigo, Michel
24 Pilipczuk, Michał
24 Raman, Venkatesh
23 Bodlaender, Hans L.
23 Caragiannis, Ioannis
23 Gutin, Gregory Z.
23 Heggernes, Pinar
23 Rothe, Jörg-Matthias
22 Brandstädt, Andreas
22 Kratsch, Dieter
22 Lampis, Michael
22 Milanič, Martin
22 Navarro, Gonzalo
22 Zehavi, Meirav
21 Guo, Jiong
21 Harks, Tobias
21 Hemaspaandra, Lane A.
21 Kratsch, Stefan
21 Panolan, Fahad
20 Bazgan, Cristina
20 Gurski, Frank
20 Kwon, O. joung
20 Maletti, Andreas
20 Mitrana, Victor
20 Monnot, Jérôme
20 Otachi, Yota
20 Pelc, Andrzej
20 Szeider, Stefan
20 Vogler, Heiko
19 Jain, Sanjay
18 Cai, Jin-Yi
18 Droste, Manfred
18 Flocchini, Paola
18 Kowalski, Dariusz R.
18 Levin, Asaf
18 Santoro, Nicola
17 Busch, Costas
17 Chen, Jian-er
17 Doerr, Benjamin
17 Nichterlein, André
17 Papadopoulos, Charis
17 Rossmanith, Peter
17 Souza, Uéverton S.
17 Xiao, Mingyu
17 Zamaraev, Victor A.
16 Bača, Martin
16 Ban, Jungchao
16 Böckenhauer, Hans-Joachim
16 Bodirsky, Manuel
16 Chang, Chih-Hung
16 Downey, Rodney Graham
16 Manea, Florin
16 Marx, Dániel
16 Monien, Burkhard
16 Rosamond, Frances A.
16 Siebertz, Sebastian
16 van Bevern, René
15 Blanchet-Sadri, Francine
15 Eiben, Eduard
15 Fraigniaud, Pierre
15 Fülöp, Zoltán
15 Hemaspaandra, Edith
15 Kanté, Mamadou Moustapha
15 Lutz, Jack H.
15 Pilipczuk, Marcin L.
15 Place, Thomas
15 Rzążewski, Paweł
15 Tamir, Tami
14 Brattka, Vasco
14 Chlebus, Bogdan Stanislaw
14 Dell, Holger
14 Diekert, Volker
14 Gaspers, Serge
14 Hitchcock, John M.
14 Hliněný, Petr
14 Kaklamanis, Christos
14 Korman, Amos
14 Kufleitner, Manfred
14 Makowsky, Johann-Andreas
...and 7,171 more Authors
all top 5

Cited in 407 Journals

782 Theoretical Computer Science
303 Algorithmica
276 Theory of Computing Systems
221 Discrete Applied Mathematics
192 Journal of Computer and System Sciences
178 Information and Computation
149 Information Processing Letters
93 Journal of Combinatorial Optimization
87 International Journal of Foundations of Computer Science
78 Distributed Computing
75 SIAM Journal on Computing
65 SIAM Journal on Discrete Mathematics
57 Logical Methods in Computer Science
50 Discrete Mathematics
43 Journal of Discrete Algorithms
35 European Journal of Operational Research
34 Annals of Pure and Applied Logic
33 Artificial Intelligence
31 Information Sciences
28 Networks
28 RAIRO. Theoretical Informatics and Applications
27 Computers & Operations Research
26 Acta Informatica
26 Computational Geometry
26 Computational Complexity
24 Mathematics of Operations Research
24 International Journal of Algebra and Computation
24 Mathematical Programming. Series A. Series B
23 Natural Computing
23 ACM Transactions on Computational Logic
22 The Journal of Symbolic Logic
22 Operations Research Letters
21 Games and Economic Behavior
21 Discrete Optimization
19 Journal of Scheduling
19 Computer Science Review
18 Journal of Graph Theory
18 European Journal of Combinatorics
18 Mathematical Structures in Computer Science
16 Journal of the ACM
16 Optimization Letters
15 Journal of Combinatorial Theory. Series B
15 Discrete & Computational Geometry
15 Journal of Parallel and Distributed Computing
15 The Journal of Artificial Intelligence Research (JAIR)
15 RAIRO. Theoretical Informatics and Applications
14 Applied Mathematics and Computation
14 Journal of Graph Algorithms and Applications
14 Algorithms
13 Journal of Algebra
13 Annals of Operations Research
13 Annals of Mathematics and Artificial Intelligence
13 ACM Journal of Experimental Algorithmics
12 Operations Research
12 The Electronic Journal of Combinatorics
12 Discrete Mathematics, Algorithms and Applications
11 Journal of Global Optimization
11 Mathematical Logic Quarterly (MLQ)
11 International Transactions in Operational Research
11 Computability
10 Advances in Applied Mathematics
10 Random Structures & Algorithms
10 ACM Transactions on Algorithms
9 International Journal of Game Theory
9 Transactions of the American Mathematical Society
9 International Journal of Computer Mathematics
9 Archive for Mathematical Logic
9 Discrete Mathematics and Theoretical Computer Science. DMTCS
9 Quantum Information Processing
9 Mathematics in Computer Science
8 Proceedings of the American Mathematical Society
8 Ergodic Theory and Dynamical Systems
8 Graphs and Combinatorics
8 Journal of Automated Reasoning
8 International Journal of Computational Geometry & Applications
8 Designs, Codes and Cryptography
8 Linear Algebra and its Applications
8 Journal of Applied Non-Classical Logics
8 The Bulletin of Symbolic Logic
8 Lobachevskii Journal of Mathematics
8 Journal of Applied Logic
8 AKCE International Journal of Graphs and Combinatorics
7 Journal of Statistical Physics
7 Automatica
7 Journal of Combinatorial Theory. Series A
7 Semigroup Forum
7 International Journal of Approximate Reasoning
7 Formal Methods in System Design
7 Journal of Automata, Languages and Combinatorics
7 Theory of Computing
7 Prikladnaya Diskretnaya Matematika
6 International Journal of Theoretical Physics
6 Algebra and Logic
6 Mathematical Social Sciences
6 Order
6 Journal of Complexity
6 Automation and Remote Control
6 Combinatorics, Probability and Computing
6 Constraints
6 Fundamenta Informaticae
...and 307 more Journals
all top 5

Cited in 53 Fields

4,542 Computer science (68-XX)
1,506 Combinatorics (05-XX)
800 Operations research, mathematical programming (90-XX)
676 Mathematical logic and foundations (03-XX)
609 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
210 Information and communication theory, circuits (94-XX)
147 Group theory and generalizations (20-XX)
111 Number theory (11-XX)
109 Dynamical systems and ergodic theory (37-XX)
98 Probability theory and stochastic processes (60-XX)
89 Biology and other natural sciences (92-XX)
82 Quantum theory (81-XX)
58 Order, lattices, ordered algebraic structures (06-XX)
55 Numerical analysis (65-XX)
50 Measure and integration (28-XX)
42 Convex and discrete geometry (52-XX)
41 Statistics (62-XX)
39 General algebraic systems (08-XX)
39 Systems theory; control (93-XX)
33 Linear and multilinear algebra; matrix theory (15-XX)
33 General topology (54-XX)
23 Statistical mechanics, structure of matter (82-XX)
18 Category theory; homological algebra (18-XX)
15 Associative rings and algebras (16-XX)
12 History and biography (01-XX)
11 Algebraic geometry (14-XX)
10 Functions of a complex variable (30-XX)
9 Operator theory (47-XX)
9 Calculus of variations and optimal control; optimization (49-XX)
8 General and overarching topics; collections (00-XX)
7 Commutative algebra (13-XX)
7 Real functions (26-XX)
6 Topological groups, Lie groups (22-XX)
6 Ordinary differential equations (34-XX)
6 Manifolds and cell complexes (57-XX)
5 Geometry (51-XX)
4 Approximations and expansions (41-XX)
4 Mechanics of deformable solids (74-XX)
3 Functional analysis (46-XX)
3 Differential geometry (53-XX)
3 Algebraic topology (55-XX)
3 Mechanics of particles and systems (70-XX)
2 Field theory and polynomials (12-XX)
2 Partial differential equations (35-XX)
2 Abstract harmonic analysis (43-XX)
2 Fluid mechanics (76-XX)
1 Nonassociative rings and algebras (17-XX)
1 \(K\)-theory (19-XX)
1 Difference and functional equations (39-XX)
1 Harmonic analysis on Euclidean spaces (42-XX)
1 Integral equations (45-XX)
1 Optics, electromagnetic theory (78-XX)
1 Relativity and gravitational theory (83-XX)

Citations by Year