×

zbMATH — the first resource for mathematics

Theory of Computing Systems

Short Title: Theory Comput. Syst.
Publisher: Springer US, New York, NY
ISSN: 1432-4350; 1433-0490/e
Online: http://link.springer.com/journal/volumesAndIssues/224
Predecessor: Mathematical Systems Theory
Comments: Indexed cover-to-cover
Documents Indexed: 1,389 Publications (since 1997)
References Indexed: 944 Publications with 23,895 References.
all top 5

Latest Issues

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)
48, No. 2 (2011)
48, No. 1 (2011)
47, No. 4 (2010)
47, No. 3 (2010)
47, No. 2 (2010)
47, No. 1 (2010)
46, No. 4 (2010)
46, No. 3 (2010)
46, No. 2 (2010)
46, No. 1 (2010)
45, No. 4 (2009)
45, No. 3 (2009)
45, No. 2 (2009)
45, No. 1 (2009)
44, No. 4 (2009)
44, No. 3 (2009)
44, No. 2 (2009)
...and 73 more Volumes
all top 5

Authors

15 Spirakis, Paul G.
12 Lohrey, Markus
11 Scheideler, Christian
10 Diekert, Volker
10 Fotakis, Dimitris A.
9 Anshelevich, Elliot
9 Kaklamanis, Christos
9 Mayordomo, Elvira
9 Niedermeier, Rolf
9 Watanabe, Osamu
8 Bilò, Vittorio
8 Bollig, Beate
8 Buhrman, Harry
8 Cai, Jin-Yi
8 Caragiannis, Ioannis
8 Epstein, Leah
8 Patt-Shamir, Boaz
8 Saurabh, Saket
7 Allender, Eric W.
7 Bergstra, Jan A.
7 Bodlaender, Hans L.
7 Carton, Olivier
7 Fomin, Fedor V.
7 Hitchcock, John M.
7 Krizanc, Danny
7 Luccio, Fabrizio
7 Mavronicolas, Marios
7 Merkle, Wolfgang
7 Meyer auf der Heide, Friedhelm
7 Raman, Venkatesh
7 Shen, Alexander
7 Thérien, Denis
7 Vogler, Heiko
6 Bauwens, Bruno
6 Bender, Michael A.
6 Dürr, Christoph
6 Fellows, Michael Ralph
6 Flammini, Michele
6 Fraigniaud, Pierre
6 Golovach, Petr A.
6 Jeż, Artur
6 Kufleitner, Manfred
6 Luccio, Flaminia L.
6 Lutz, Jack H.
6 McNicholl, Timothy H.
6 Monien, Burkhard
6 Rosenberg, Arnold Leonard
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 Langerman, Stefan
5 Mahajan, Meena
5 Muscholl, Anca
5 Nikoletseas, Sotiris E.
5 Ogihara, Mitsunori
5 Okhotin, Alexander
5 Pavan, Aduri
5 Persiano, Giuseppe
5 Pilipczuk, Marcin
5 Pucci, Geppino
5 Rosamond, Frances A.
5 Rossmanith, Peter
5 Rothe, Jörg-Matthias
5 Serna, Maria José
5 Stephan, Frank
4 Adler, Micah
4 Albers, Susanne
4 Barceló, Pablo
4 Brandt, Felix
4 Cenzer, Douglas
4 Demaine, Erik D.
4 Downey, Rodney Graham
4 Droste, Manfred
4 Durand, Arnaud
4 Fanelli, Angelo
4 Fischer, Felix
4 Flocchini, Paola
4 Freydenberger, Dominik D.
4 Geerts, Floris
4 Guo, Jiong
4 Gutin, Gregory Z.
4 Hansen, Kristoffer Arnsfelt
4 Harks, Tobias
4 Hirsch, Edward A.
4 Hoyrup, Mathieu
4 Jurdziński, Tomasz
4 Karhumaki, Juhani
4 Koucký, Michal
4 Koutris, Paraschos
...and 2,124 more Authors

Publications by Year

Citations contained in zbMATH Open

867 Publications have been cited 4,526 times in 3,841 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.
268
2000
Polynomial closure and unambiguous product. Zbl 0872.68119
Pin, J.-E.; Weil, P.
57
1997
Compressed suffix trees with full functionality. Zbl 1148.68015
Sadakane, Kunihiko
50
2007
On covering problems of codes. Zbl 0868.94056
Frances, M.; Litman, A.
44
1997
Graph-modeled data clustering: Exact algorithms for clique generation. Zbl 1084.68117
Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf
44
2005
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
37
2008
Upper and lower bounds for randomized search heuristics in black-box optimization. Zbl 1103.68115
Droste, Stefan; Jansen, Thomas; Wegener, Ingo
37
2006
Network design with weighted players. Zbl 1176.91003
Chen, Ho-Lin; Roughgarden, Tim
35
2009
Gradient clock synchronization in dynamic networks. Zbl 1253.68060
Kuhn, Fabian; Locher, Thomas; Oshman, Rotem
34
2011
Finite presentations of infinite structures: Automata and interpretations. Zbl 1061.03038
Blumensath, Achim; Grädel, Erich
33
2004
Approximate equilibria and ball fusion. Zbl 1101.68336
Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul
32
2003
Applying modular decomposition to parameterized cluster editing problems. Zbl 1179.68111
Protti, Fábio; Dantas da Silva, Maise; Szwarcfiter, Jayme Luiz
32
2009
Fixed-parameter algorithms for cluster vertex deletion. Zbl 1205.68263
Hüffner, Falk; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf
32
2010
Numeration systems on a regular language. Zbl 0969.68095
Lecomte, P. B. A.; Rigo, M.
30
2001
Nearest common ancestors: a survey and a new algorithm for a distributed environment. Zbl 1093.68136
Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis
29
2004
Crown structures for vertex cover kernelization. Zbl 1148.68035
Abu-Khzam, Faisal N.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry
29
2007
A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Zbl 0896.68080
Staiger, L.
26
1998
Complexity of Presburger arithmetic with fixed quantifier dimension. Zbl 0872.68048
Schöning, U.
25
1997
Balanced graph partitioning. Zbl 1113.68069
Andreev, Konstantin; Räcke, Harald
25
2006
Generating shorter bases for hard random lattices. Zbl 1217.94092
Alwen, Joël; Peikert, Chris
25
2011
Exact complexity of the winner problem for Young elections. Zbl 1061.90084
Rothe, Jörg; Spakowski, Holger; Vogel, Jörg
24
2003
Equational elements in additive algebras. Zbl 0914.68118
Bozapalidis, S.
23
1999
Undecidable problems for probabilistic automata of fixed dimension. Zbl 1039.68061
Blondel, Vincent D.; Canterini, Vincent
23
2003
Algebraic results on quantum automata. Zbl 1101.68029
Ambainis, Andris; Beaudry, Martin; Golovkins, Marats; Kikusts, Arnolds; Mercer, Mark; Therien, Denis
23
2006
Clique-width for 4-vertex forbidden subgraphs. Zbl 1103.68088
Brandstädt, Andreas; Engelfriet, Joost; Le, Hoang-Oanh; Lozin, Vadim V.
23
2006
Accessing nearby copies of replicated objects in a distributed environment. Zbl 0929.68126
Plaxton, C. G.; Rajaraman, R.; Richa, A. W.
22
1999
Parameterized complexity of Vertex Cover variants. Zbl 1147.68607
Guo, Jiong; Niedermeier, Rolf; Wernicke, Sebastian
22
2007
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327
Jeż, Artur; Okhotin, Alexander
22
2010
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
21
2009
On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109
Berman, P.; Fujito, T.
20
1999
The power of commuting with finite sets of words. Zbl 1121.68065
Kunc, Michal
20
2007
Descendants of primitive substitutions. Zbl 0916.68086
Holton, C.; Zamboni, L. Q.
19
1999
New graph classes of bounded clique-width. Zbl 1084.68088
Brandstädt, Andreas; Dragan, Feodor F.; Le, Hoàng-Oanh; Mosca, Raffaele
19
2005
Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter. Zbl 1286.68196
Jansen, Bart M. P.; Bodlaender, Hans L.
19
2013
On edge irregular total labeling of categorical product of two cycles. Zbl 1284.05232
Ahmad, Ali; Bača, Martin; Siddiqui, Muhammad Kamran
18
2014
A generalization of Cobham’s theorem. Zbl 0895.68081
Durand, F.
18
1998
Efficient exact algorithms through enumerating maximal independent sets and other techniques. Zbl 1148.68054
Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath
18
2007
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
18
2007
The hub number of Sierpiński-like graphs. Zbl 1234.05178
Lin, Chien-Hung; Liu, Jia-Jie; Wang, Yue-Li; Yen, William Chung-Kung
18
2011
Local MST computation with short advice. Zbl 1213.68123
Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle
18
2010
The efficiency of fair division. Zbl 1262.91099
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria
17
2012
Irregular total labellings of generalized Petersen graphs. Zbl 1254.05172
Haque, Khandoker Mohammed Mominul
17
2012
DNA computing based on splicing: The existence of universal computers. Zbl 0914.68072
Freund, R.; Kari, L.; Păun, Gh.
16
1999
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
Correspondence principles for effective dimensions. Zbl 1084.68054
Hitchcock, John M.
16
2005
Dynamic programming for minimum Steiner trees. Zbl 1148.68038
Fuchs, B.; Kern, W.; Molle, D.; Richter, S.; Rossmanith, P.; Wang, X.
16
2007
The linear arrangement problem parameterized above guaranteed value. Zbl 1148.68039
Gutin, Gregory; Rafiey, Arash; Szeider, Stefan; Yeo, Anders
16
2007
Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Zbl 1148.68041
Mölle, Daniel; Richter, Stefan; Rossmanith, Peter
16
2008
From a zoo to a zoology: Towards a general theory of graph polynomials. Zbl 1162.68502
Makowsky, J. A.
16
2008
Simple and improved parameterized algorithms for multiterminal cuts. Zbl 1213.68472
Xiao, Mingyu
16
2010
A cubic kernel for feedback vertex set and loop cutset. Zbl 1215.68170
Bodlaender, Hans L.; van Dijk, Thomas C.
16
2010
Randomness on computable probability spaces – a dynamical point of view. Zbl 1238.68069
Gács, Peter; Hoyrup, Mathieu; Rojas, Cristóbal
15
2011
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.
15
2012
On approximate jumbled pattern matching in strings. Zbl 1253.68372
Burcsi, Péter; Cicalese, Ferdinando; Fici, Gabriele; Lipták, Zsuzsanna
15
2012
Constant thresholds can make target set selection tractable. Zbl 1319.68109
Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias
14
2014
A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
14
2016
Stackelberg strategies for atomic congestion games. Zbl 1203.91035
Fotakis, Dimitris
14
2010
First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Zbl 0904.68137
Muthukrishnan, S.; Ghosh, B.; Schultz, M. H.
13
1998
Automatic maps in exotic numeration systems. Zbl 0870.68105
Allouche, Jean-Paul; Cateland, E.; Gilbert, W. J.; Peitgen, Heinz-Otto; Shallit, Jeffrey O.; Skordev, Gencho
13
1997
Distributed streams algorithms for sliding windows. Zbl 1093.68143
Gibbons, Phillip B.; Tirthapura, Srikanta
13
2004
A Kleene theorem for weighted tree automata. Zbl 1061.68092
Droste, Manfred; Pech, Christian; Vogler, Heiko
13
2005
On the uniform computational content of computability theory. Zbl 1420.03110
Brattka, Vasco; Hendtlass, Matthew; Kreuzer, Alexander P.
13
2017
The complexity of equality constraint languages. Zbl 1148.68025
Bodirsky, Manuel; Kára, Jan
13
2008
Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications. Zbl 1175.90366
Tsaggouris, George; Zaroliagis, Christos
13
2009
A new characterization of NP, P, and PSPACE with accepting hybrid networks of evolutionary processors. Zbl 1209.68264
Manea, Florin; Margenstern, Maurice; Mitrana, Victor; Pérez-Jiménez, Mario J.
13
2010
Real hypercomputation and continuity. Zbl 1122.03039
Ziegler, Martin
13
2007
Complexity of equations over sets of natural numbers. Zbl 1209.68263
Jeż, Artur; Okhotin, Alexander
13
2011
Sofic tree-shifts. Zbl 1293.68195
Aubrun, Nathalie; Béal, Marie-Pierre
13
2013
Computing the maximum overlap of two convex polygons under translations. Zbl 0910.68226
de Berg, M.; Cheong, O.; Devillers, O.; van Kreveld, M.; Teillaud, M.
12
1998
Hamiltonicity of the hierarchical cubic network. Zbl 0993.68003
Fu, Jung-Sheng; Chen, Gen-Huey
12
2002
Characterizing the micronuclear gene patterns in ciliates. Zbl 1001.68903
Ehrenfeucht, Andrzej; Harju, Tero; Petre, Ion; Rozenberg, Grzegorz
12
2002
The mortality problem for matrices of low dimensions. Zbl 1016.68038
Bournez, O.; Branicky, M.
12
2002
Regular languages and Stone duality. Zbl 0870.68092
Pippenger, N.
12
1997
The bell is ringing in speed-scaled multiprocessor scheduling. Zbl 1310.68048
Greiner, Gero; Nonner, Tim; Souza, Alexander
12
2014
Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022
Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola
12
2007
Fixed-parameter enumerability of cluster editing and related problems. Zbl 1209.68360
Damaschke, Peter
12
2010
Exact algorithms for graph homomorphisms. Zbl 1119.68133
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter
12
2007
Weighted logics for unranked tree automata. Zbl 1226.03048
Droste, Manfred; Vogler, Heiko
12
2011
Stackelberg strategies and collusion in network games with splittable flow. Zbl 1213.91043
Harks, Tobias
12
2011
The rank-width of edge-coloured graphs. Zbl 1269.05036
Kanté, Mamadou Moustapha; Rao, Michael
12
2013
Thread scheduling for multiprogrammed multiprocessors. Zbl 0978.68020
Arora, N. S.; Blumofe, R. D.; Plaxton, C. G.
11
2001
On multidimensional curves with Hilbert property. Zbl 0960.68161
Alber, J.; Niedermeier, R.
11
2000
Bounding the expected length of longest common subsequences and forests. Zbl 0934.68043
Baeza-Yates, R. A.; Gavaldá, R.; Navarro, G.; Scheihing, R.
11
1999
Directed graphs and substitutions. Zbl 0993.68075
Holton, C.; Zamboni, L. Q.
11
2001
Space efficient hash tables with worst case constant access time. Zbl 1066.68025
Fotakis, Dimitris; Pagh, Rasmus; Sanders, Peter; Spirakis, Paul
11
2005
\(\frac{13}{9}\)-approximation for graphic TSP. Zbl 1319.68255
Mucha, Marcin
11
2014
On the hardness of losing width. Zbl 1290.68045
Cygan, Marek; Lokshtanov, Daniel; Pilipczuk, Marcin; Pilipczuk, Michał; Saurabh, Saket
11
2014
Fixed points, Nash equilibria, and the existential theory of the reals. Zbl 1362.68088
Schaefer, Marcus; Štefankovič, Daniel
11
2017
The hardness of approximating spanner problems. Zbl 1148.68024
Elkin, Michael; Peleg, David
11
2007
Online removable square packing. Zbl 1135.90434
Han, Xin; Iwama, Kazuo; Zhang, Guochuan
11
2008
Energy-efficient wireless network design. Zbl 1100.68505
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis
11
2006
Solving the 2-disjoint paths problem in nearly linear time. Zbl 1103.68100
Tholey, Torsten
11
2006
Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs. Zbl 1170.90461
Athanassopoulos, Stavros; Caragiannis, Ioannis; Kaklamanis, Christos
11
2009
Characterizing the existence of potential functions in weighted congestion games. Zbl 1278.91013
Harks, Tobias; Klimm, Max; Möhring, Rolf H.
11
2011
Trimmed Moebius inversion and graphs of bounded degree. Zbl 1225.05005
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko
11
2010
Vertex cover problem parameterized above and below tight bounds. Zbl 1209.68276
Gutin, Gregory; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia
11
2011
Lower bounds for kernelizations and other preprocessing procedures. Zbl 1234.68118
Chen, Yijia; Flum, Jörg; Müller, Moritz
11
2011
Improved lower bounds on the price of stability of undirected network design games. Zbl 1273.90168
Bilò, Vittorio; Caragiannis, Ioannis; Fanelli, Angelo; Monaco, Gianpiero
11
2013
The equivalence problem of polynomially bounded D0L systems – a bound depending only on the size of the alphabet. Zbl 1039.68067
Honkala, Juha
10
2003
Quotient complexity of closed languages. Zbl 1380.68249
Brzozowski, Janusz; Jirásková, Galina; Zou, Chenglong
10
2014
Semi-oblivious chase termination: the sticky case. Zbl 07363117
Calautti, Marco; Pieris, Andreas
1
2021
On tseitin formulas, read-once branching programs and treewidth. Zbl 07377746
Glinskih, Ludmila; Itsykson, Dmitry
1
2021
Token sliding on split graphs. Zbl 07379111
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian
1
2021
Complexity and inapproximability results for parallel task scheduling and strip packing. Zbl 07175458
Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars
1
2020
New bounds for truthful scheduling on two unrelated selfish machines. Zbl 1434.68678
Kuryatnikova, Olga; Vera, Juan C.
1
2020
Conflict free version of covering problems on graphs: classical and parameterized. Zbl 1453.68136
Jain, Pallavi; Kanesh, Lawqueen; Misra, Pranabendu
1
2020
Computing hitting set kernels by \(\mathrm{AC}^0\)-circuits. Zbl 1433.68177
Bannach, Max; Tantau, Till
1
2020
Lower bound techniques for QBF expansion. Zbl 07189478
Beyersdorff, Olaf; Blinkhorn, Joshua
1
2020
On the tree conjecture for the network creation game. Zbl 1443.91071
Bilò, Davide; Lenzner, Pascal
1
2020
Optimal dislocation with persistent errors in subquadratic time. Zbl 1433.68111
Geissmann, Barbara; Leucci, Stefano; Liu, Chih-Hung; Penna, Paolo
1
2020
On the stab number of rectangle intersection graphs. Zbl 1442.05187
Chakraborty, Dibyayan; Francis, Mathew C.
1
2020
On limitations of structured (deterministic) DNNFs. Zbl 1446.68152
Bollig, Beate; Buttkus, Matthias
1
2020
The operator approach to entropy games. Zbl 1422.91080
Akian, Marianne; Gaubert, Stéphane; Grand-Clément, Julien; Guillaud, Jérémie
3
2019
On the relative succinctness of sentential decision diagrams. Zbl 1435.68320
Bollig, Beate; Buttkus, Matthias
3
2019
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68114
Verbitsky, Oleg; Zhukovskii, Maksim
2
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.
2
2019
Designing cost-sharing methods for Bayesian games. Zbl 1409.91147
Christodoulou, George; Leonardi, Stefano; Sgouritsa, Alkmini
1
2019
Price of anarchy for highly congested routing games in parallel networks. Zbl 1411.91136
Colini-Baldeschi, Riccardo; Cominetti, Roberto; Scarsini, Marco
1
2019
An almost ideal coordination mechanism for unrelated machine scheduling. Zbl 1411.90108
Caragiannis, Ioannis; Fanelli, Angelo
1
2019
The stable roommates problem with short lists. Zbl 1418.91387
Cseh, Ágnes; Irving, Robert W.; Manlove, David F.
1
2019
On-line path computation and function placement in SDNs. Zbl 1423.68046
Even, Guy; Medina, Moti; Patt-Shamir, Boaz
1
2019
Pattern matching and consensus problems on weighted sequences and profiles. Zbl 1423.68620
Kociumaka, Tomasz; Pissis, Solon P.; Radoszewski, Jakub
1
2019
A unifying approach to algebraic systems over semirings. Zbl 1431.68067
Kostolányi, Peter
1
2019
Verification of quantum computation: an overview of existing approaches. Zbl 1423.68281
Gheorghiu, Alexandru; Kapourniotis, Theodoros; Kashefi, Elham
1
2019
Comparing linear width parameters for directed graphs. Zbl 1420.05068
Gurski, Frank; Rehs, Carolin
1
2019
Online random sampling for budgeted settings. Zbl 1422.91301
Eden, Alon; Feldman, Michal; Vardi, Adi
1
2019
Tighter bounds and optimal algorithms for all maximal \(\alpha\)-gapped repeats and palindromes. Finding all maximal \(\alpha\)-gapped repeats and palindromes in optimal worst case time on integer alphabets. Zbl 1386.68120
Gawrychowski, Paweł; I, Tomohiro; Inenaga, Shunsuke; Köppl, Dominik; Manea, Florin
5
2018
Co-c.e. sets with disconnected complements. Zbl 1436.03231
Iljazović, Zvonko; Pažek, Bojan
5
2018
Finite-state independence. Zbl 1404.68066
Becher, Verónica; Carton, Olivier; Heiber, Pablo Ariel
4
2018
Exploration of the \(T\)-interval-connected dynamic graphs: the case of the ring. Zbl 1392.68099
Ilcinkas, David; Wade, Ahmed M.
4
2018
A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Zbl 1394.91015
Bilò, Vittorio
4
2018
Faster algorithms for the constrained \(k\)-means problem. Zbl 1387.68296
Bhattacharya, Anup; Jaiswal, Ragesh; Kumar, Amit
3
2018
Testing shape restrictions of discrete distributions. Zbl 1386.68215
Canonne, Clément L.; Diakonikolas, Ilias; Gouleakis, Themis; Rubinfeld, Ronitt
2
2018
A randomized polynomial kernel for subset feedback vertex set. Zbl 1387.68134
Hols, Eva-Maria C.; Kratsch, Stefan
2
2018
Knapsack in graph groups. Zbl 1386.68073
Lohrey, Markus; Zetzsche, Georg
2
2018
Syntactic complexity of regular ideals. Zbl 1398.68301
Brzozowski, Janusz A.; Szykuła, Marek; Ye, Yuli
2
2018
Collaborative exploration of trees by energy-constrained mobile robots. Zbl 1392.68412
Das, Shantanu; Dereniowski, Dariusz; Karousatou, Christina
2
2018
Finding cactus roots in polynomial time. Zbl 1391.68052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
2
2018
Partial covering arrays: algorithms and asymptotics. Zbl 1391.68085
Sarkar, Kaushik; Colbourn, Charles J.; De Bonis, Annalisa; Vaccaro, Ugo
2
2018
Space efficient linear time algorithms for BFS, DFS and applications. Zbl 1430.68173
Banerjee, Niranka; Chakraborty, Sankardeep; Raman, Venkatesh; Satti, Srinivasa Rao
2
2018
Polynomial kernels for vertex cover parameterized by small degree modulators. Zbl 1419.05179
Majumdar, Diptapriyo; Raman, Venkatesh; Saurabh, Saket
2
2018
Shortest augmenting paths for online matchings on trees. Zbl 1390.68768
Bosek, Bartłomiej; Leniowski, Dariusz; Sankowski, Piotr; Zych-Pawlewicz, Anna
2
2018
Efficient vertex-label distance oracles for planar graphs. Zbl 1390.68507
Mozes, Shay; Skop, Eyal E.
2
2018
Approximation algorithms for connected graph factors of minimum weight. Zbl 1390.68760
Cornelissen, Kamiel; Hoeksma, Ruben; Manthey, Bodo; Narayanaswamy, N. S.; Rahul, C. S.; Waanders, Marten
2
2018
Tropically convex constraint satisfaction. Zbl 1390.68333
Bodirsky, Manuel; Mamino, Marcello
2
2018
Improved approximation algorithms for minimum cost node-connectivity augmentation problems. Zbl 1394.68443
Nutov, Zeev
2
2018
Document spanners: from expressive power to decision problems. Zbl 1392.68167
Freydenberger, Dominik D.; Holldack, Mario
2
2018
Catalytic space: non-determinism and hierarchy. Zbl 1387.68109
Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian
1
2018
The complexity of tensor rank. Zbl 1396.68061
Schaefer, Marcus; Štefankovič, Daniel
1
2018
On effective Birkhoff’s ergodic theorem for computable actions of amenable groups. Zbl 1436.03234
Moriakov, Nikita
1
2018
Homonym population protocols. Zbl 1392.68095
Bournez, Olivier; Cohen, Johanne; Rabie, Mikaël
1
2018
Minimax regret 1-median problem in dynamic path networks. Zbl 1397.90236
Higashikawa, Yuya; Cheng, Siu-Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun
1
2018
Weighted online problems with advice. Zbl 1391.68127
Boyar, Joan; Favrholdt, Lene M.; Kudahl, Christian; Mikkelsen, Jesper W.
1
2018
Revisiting connected vertex cover: FPT algorithms and lossy kernels. Zbl 1430.68225
Krithika, R.; Majumdar, Diptapriyo; Raman, Venkatesh
1
2018
Parameterised algorithms for deletion to classes of DAGs. Zbl 1430.68170
Agrawal, Akanksha; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav
1
2018
Online bin packing with advice of small size. Zbl 1435.68384
Angelopoulos, Spyros; Dürr, Christoph; Kamali, Shahin; Renault, Marc P.; Rosén, Adi
1
2018
Geometric hitting set for segments of few orientations. Zbl 1384.68021
Fekete, Sándor P.; Huang, Kan; Mitchell, Joseph S. B.; Parekh, Ojas; Phillips, Cynthia A.
1
2018
Tight bounds for double coverage against weak adversaries. Zbl 1390.68767
Bansal, Nikhil; Eliáš, Marek; Jeż, Łukasz; Koumoutsos, Grigorios; Pruhs, Kirk
1
2018
Level two of the quantifier alternation hierarchy over infinite words. Zbl 1436.03216
Kufleitner, Manfred; Walter, Tobias
1
2018
Comparing representations for function spaces in computable analysis. Zbl 1436.03241
Pauly, Arno; Steinberg, Florian
1
2018
Computing and listing \(st\)-paths in public transportation networks. Zbl 1393.68194
Böhmová, Kateřina; Häfliger, Luca; Mihalák, Matúš; Pröger, Tobias; Sacomoto, Gustavo; Sagot, Marie-France
1
2018
Parameterizing edge modification problems above lower bounds. Zbl 1386.68075
van Bevern, René; Froese, Vincent; Komusiewicz, Christian
1
2018
On the uniform computational content of computability theory. Zbl 1420.03110
Brattka, Vasco; Hendtlass, Matthew; Kreuzer, Alexander P.
13
2017
Fixed points, Nash equilibria, and the existential theory of the reals. Zbl 1362.68088
Schaefer, Marcus; Štefankovič, Daniel
11
2017
The complexity of optimal design of temporally connected graphs. Zbl 1379.68250
Akrida, Eleni C.; Gąsieniec, Leszek; Mertzios, George B.; Spirakis, Paul G.
9
2017
The behavior of clique-width under graph operations and graph transformations. Zbl 1358.05239
Gurski, Frank
7
2017
The advice complexity of a class of hard online problems. Zbl 1387.68302
Boyar, Joan; Favrholdt, Lene M.; Kudahl, Christian; Mikkelsen, Jesper W.
5
2017
Parameterized complexity of secluded connectivity problems. Zbl 1378.68075
Fomin, Fedor V.; Golovach, Petr A.; Karpov, Nikolay; Kulikov, Alexander S.
4
2017
Adversarial multiple access channels with individual injection rates. Zbl 1410.68379
Anantharamu, Lakshmi; Chlebus, Bogdan S.; Rokicki, Mariusz A.
4
2017
New pairwise spanners. Zbl 1386.05185
Kavitha, Telikepalli
3
2017
Polynomial kernelization for removing induced claws and diamonds. Zbl 1368.68222
Cygan, Marek; Pilipczuk, Marcin; Pilipczuk, Michał; van Leeuwen, Erik Jan; Wrochna, Marcin
3
2017
Paradigms for parameterized enumeration. Zbl 1368.68221
Creignou, Nadia; Meier, Arne; Müller, Julian-Steffen; Schmidt, Johannes; Vollmer, Heribert
3
2017
Composition closure of linear extended top-down tree transducers. Zbl 1369.68252
Engelfriet, Joost; Fülöp, Zoltán; Maletti, Andreas
2
2017
Sophistication vs logical depth. Zbl 1369.68248
Antunes, Luís; Bauwens, Bruno; Souto, André; Teixeira, Andreia
2
2017
Towards an isomorphism dichotomy for hereditary graph classes. Zbl 1380.68232
Schweitzer, Pascal
2
2017
Conditional probabilities and van Lambalgen’s theorem revisited. Zbl 1420.03099
Bauwens, Bruno; Shen, Alexander; Takahashi, Hayato
2
2017
Layerwise computability and image randomness. Zbl 1395.68159
Bienvenu, Laurent; Hoyrup, Mathieu; Shen, Alexander
2
2017
Short lists with short programs from programs of functions and strings. Zbl 1423.03140
Vereshchagin, Nikolay
2
2017
Regular queries on graph databases. Zbl 1375.68047
Reutter, Juan L.; Romero, Miguel; Vardi, Moshe Y.
2
2017
From causes for database queries to repairs and model-based diagnosis and back. Zbl 1370.68068
Bertossi, Leopoldo; Salimi, Babak
2
2017
Generalized LR parsing algorithm for grammars with one-sided contexts. Zbl 1379.68192
Barash, Mikhail; Okhotin, Alexander
2
2017
Online regenerator placement. Zbl 1372.90034
Mertzios, George B.; Shalom, Mordechai; Wong, Prudence W. H.; Zaks, Shmuel
2
2017
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth. Zbl 1378.68035
Razgon, Igor
2
2017
Genericity of weakly computable objects. Zbl 1366.68056
Hoyrup, Mathieu
2
2017
2-stack sorting is polynomial. Zbl 1429.68055
Pierrot, Adeline; Rossin, Dominique
2
2017
Tight lower and upper bounds for the complexity of canonical colour refinement. Zbl 1368.68219
Berkholz, Christoph; Bonsma, Paul; Grohe, Martin
2
2017
Incremental problems in the parameterized complexity setting. Zbl 1362.68111
Mans, Bernard; Mathieson, Luke
1
2017
Notes on computable analysis. Zbl 1420.03114
Porter, Michelle; Day, Adam; Downey, Rodney
1
2017
Distance vector-based advance reservation with delay performance guarantees. Zbl 1362.68027
Fazlollahi, Niloofar; Starobinski, David
1
2017
Conditional measure and the violation of van Lambalgen’s theorem for Martin-Löf randomness. Zbl 1420.03098
Bauwens, Bruno
1
2017
Editorial: Special issue on “Theoretical aspects of computer science” (STACS 2015). Zbl 1386.00076
Mayr, Ernst W.
1
2017
Minimum-cost flows in unit-capacity networks. Zbl 1379.05049
Goldberg, Andrew V.; Hed, Sagi; Kaplan, Haim; Tarjan, Robert E.
1
2017
Dynamic planar embeddings of dynamic graphs. Zbl 1387.68182
Holm, Jacob; Rotenberg, Eva
1
2017
Characterisation of limit measures of higher-dimensional cellular automata. Zbl 1430.68157
Delacourt, Martin; Hellouin de Menibus, Benjamin
1
2017
Semiautomatic structures. Zbl 1420.03072
Jain, Sanjay; Khoussainov, Bakhadyr; Stephan, Frank; Teng, Dan; Zou, Siyuan
1
2017
On the complexity of automatic complexity. Zbl 1387.68158
Kjos-Hanssen, Bjørn
1
2017
Optimal broadcasting strategies for conjunctive queries over distributed data. Zbl 1370.68069
Ketsman, Bas; Neven, Frank
1
2017
Space saving by dynamic algebraization based on tree-depth. Zbl 1379.68379
Fürer, Martin; Yu, Huiwen
1
2017
On compiling structured CNFs to OBDDs. Zbl 1378.68028
Bova, Simone; Slivovsky, Friedrich
1
2017
New bounds and extended relations between prefix arrays, border arrays, undirected graphs, and indeterminate strings. Zbl 1366.68222
Blanchet-Sadri, F.; Bodnar, Michelle; De Winkle, Benjamin
1
2017
...and 767 more Documents
all top 5

Cited by 5,091 Authors

37 Saurabh, Saket
33 Niedermeier, Rolf
31 Lozin, Vadim Vladislavovich
29 Fomin, Fedor V.
25 Golovach, Petr A.
24 Okhotin, Alexander
23 Courcelle, Bruno
22 Lohrey, Markus
22 Paulusma, Daniël
21 Ganian, Robert
21 Heggernes, Pinar
20 Fellows, Michael Ralph
20 Lokshtanov, Daniel
20 Rigo, Michel
19 Bazgan, Cristina
19 Bilò, Vittorio
19 Hemaspaandra, Lane A.
19 Kratsch, Dieter
19 Stephan, Frank
18 Brandstädt, Andreas
18 Epstein, Leah
18 Guo, Jiong
18 Komusiewicz, Christian
18 Navarro, Gonzalo
17 Bodlaender, Hans L.
17 Chen, Jian-er
17 Kratsch, Stefan
17 Mitrana, Victor
17 Santoro, Nicola
16 Caragiannis, Ioannis
16 Flocchini, Paola
16 Pelc, Andrzej
16 Spirakis, Paul G.
15 Dabrowski, Konrad Kazimierz
15 Pilipczuk, Michał
15 Raman, Venkatesh
15 Rothe, Jörg-Matthias
15 Vogler, Heiko
14 Fernau, Henning
14 Gurski, Frank
14 Gutin, Gregory Z.
14 Korman, Amos
14 Milanič, Martin
14 Paschos, Vangelis Th.
13 Bača, Martin
13 Downey, Rodney Graham
13 Fraigniaud, Pierre
13 Jansen, Bart M. P.
13 Lampis, Michael
13 Mavronicolas, Marios
13 Mnich, Matthias
13 Rossmanith, Peter
13 Szeider, Stefan
12 Brattka, Vasco
12 Diekert, Volker
12 Doerr, Benjamin
12 Fülöp, Zoltán
12 Harks, Tobias
12 Hitchcock, John M.
12 Jain, Sanjay
12 Jeż, Artur
12 Kaklamanis, Christos
12 Maletti, Andreas
12 Monnot, Jérôme
12 Pilipczuk, Marcin
12 Wang, Jianxin
12 Zamaraev, Victor A.
12 Zehavi, Meirav
11 Bergstra, Jan A.
11 Blanchet-Sadri, Francine
11 Bollig, Beate
11 Carton, Olivier
11 Censor-Hillel, Keren
11 Dell, Holger
11 Droste, Manfred
11 Glaßer, Christian
11 Han, Xin
11 Hliněný, Petr
11 Kowalski, Dariusz R.
11 Krebs, Andreas
11 Kufleitner, Manfred
11 Makowsky, Johann-Andreas
11 Manea, Florin
11 Protti, Fábio
11 Rosamond, Frances A.
11 Selivanov, Viktor L’vovich
11 Yukna, Stasys P.
10 Chang, Chih-Hung
10 Cygan, Marek
10 Escoffier, Bruno
10 Gaspers, Serge
10 Hemaspaandra, Edith
10 Kanj, Iyad A.
10 Kuske, Dietrich
10 Kwon, Ojoung
10 Liedloff, Mathieu
10 Lutz, Jack H.
10 Meister, Daniel
10 Mosca, Raffaele
10 Rautenbach, Dieter
...and 4,991 more Authors
all top 5

Cited in 321 Journals

641 Theoretical Computer Science
244 Theory of Computing Systems
234 Algorithmica
189 Discrete Applied Mathematics
150 Journal of Computer and System Sciences
132 Information Processing Letters
121 Information and Computation
71 International Journal of Foundations of Computer Science
69 Distributed Computing
63 Journal of Combinatorial Optimization
43 Journal of Discrete Algorithms
41 SIAM Journal on Computing
39 Discrete Mathematics
31 SIAM Journal on Discrete Mathematics
28 Annals of Pure and Applied Logic
28 RAIRO. Theoretical Informatics and Applications
26 Logical Methods in Computer Science
24 Information Sciences
24 European Journal of Operational Research
22 Artificial Intelligence
22 Computational Geometry
21 Computational Complexity
20 Acta Informatica
19 Discrete Optimization
18 The Journal of Symbolic Logic
18 Computers & Operations Research
16 Mathematics of Operations Research
16 International Journal of Algebra and Computation
15 European Journal of Combinatorics
15 Journal of Parallel and Distributed Computing
15 Games and Economic Behavior
14 Operations Research Letters
14 Journal of Scheduling
14 Algorithms
13 Optimization Letters
13 Computer Science Review
12 Applied Mathematics and Computation
12 Journal of Combinatorial Theory. Series B
11 Mathematical Programming. Series A. Series B
11 Natural Computing
11 ACM Transactions on Computational Logic
11 RAIRO. Theoretical Informatics and Applications
10 Operations Research
10 MSCS. Mathematical Structures in Computer Science
10 Annals of Mathematics and Artificial Intelligence
10 Journal of the ACM
9 Journal of Graph Theory
9 Annals of Operations Research
9 International Journal of Computer Mathematics
9 Mathematics in Computer Science
8 Journal of Algebra
8 Networks
8 Transactions of the American Mathematical Society
8 Advances in Applied Mathematics
8 Discrete & Computational Geometry
8 International Journal of Computational Geometry & Applications
8 Linear Algebra and its Applications
8 Mathematical Logic Quarterly (MLQ)
8 Journal of Applied Logic
7 Journal of Statistical Physics
7 Ergodic Theory and Dynamical Systems
7 Journal of Global Optimization
7 Discrete Mathematics, Algorithms and Applications
6 International Journal of Game Theory
6 Proceedings of the American Mathematical Society
6 Semigroup Forum
6 Journal of Complexity
6 Journal of Automated Reasoning
6 International Journal of Approximate Reasoning
6 Random Structures & Algorithms
6 Journal of Applied Non-Classical Logics
6 The Bulletin of Symbolic Logic
6 ACM Journal of Experimental Algorithmics
5 Algebra and Logic
5 Annales de l’Institut Fourier
5 Automatica
5 Fuzzy Sets and Systems
5 Journal of Combinatorial Theory. Series A
5 Graphs and Combinatorics
5 Automation and Remote Control
5 International Transactions in Operational Research
5 Lobachevskii Journal of Mathematics
5 Internet Mathematics
4 Mathematics of Computation
4 Advances in Mathematics
4 Algebra Universalis
4 Computing
4 Journal of Mathematical Economics
4 Studia Logica
4 Topology and its Applications
4 Mathematical Social Sciences
4 Order
4 Journal of Symbolic Computation
4 Stochastic Processes and their Applications
4 Archive for Mathematical Logic
4 Indagationes Mathematicae. New Series
4 Formal Methods in System Design
4 Combinatorics, Probability and Computing
4 Journal of Mathematical Sciences (New York)
4 The Journal of Artificial Intelligence Research (JAIR)
...and 221 more Journals
all top 5

Cited in 50 Fields

2,842 Computer science (68-XX)
1,008 Combinatorics (05-XX)
503 Operations research, mathematical programming (90-XX)
432 Mathematical logic and foundations (03-XX)
347 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
117 Information and communication theory, circuits (94-XX)
95 Group theory and generalizations (20-XX)
75 Dynamical systems and ergodic theory (37-XX)
68 Number theory (11-XX)
68 Biology and other natural sciences (92-XX)
61 Probability theory and stochastic processes (60-XX)
46 Numerical analysis (65-XX)
36 Convex and discrete geometry (52-XX)
36 Quantum theory (81-XX)
34 Order, lattices, ordered algebraic structures (06-XX)
33 Measure and integration (28-XX)
26 General topology (54-XX)
26 Systems theory; control (93-XX)
22 General algebraic systems (08-XX)
19 Linear and multilinear algebra; matrix theory (15-XX)
18 Statistics (62-XX)
11 Statistical mechanics, structure of matter (82-XX)
10 History and biography (01-XX)
9 Associative rings and algebras (16-XX)
9 Operator theory (47-XX)
8 Category theory; homological algebra (18-XX)
7 Functions of a complex variable (30-XX)
6 Real functions (26-XX)
5 General and overarching topics; collections (00-XX)
5 Commutative algebra (13-XX)
4 Algebraic geometry (14-XX)
4 Topological groups, Lie groups (22-XX)
4 Calculus of variations and optimal control; optimization (49-XX)
4 Geometry (51-XX)
4 Mechanics of deformable solids (74-XX)
3 Approximations and expansions (41-XX)
3 Functional analysis (46-XX)
3 Manifolds and cell complexes (57-XX)
2 Ordinary differential equations (34-XX)
2 Partial differential equations (35-XX)
2 Differential geometry (53-XX)
2 Mechanics of particles and systems (70-XX)
1 Field theory and polynomials (12-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 Global analysis, analysis on manifolds (58-XX)
1 Optics, electromagnetic theory (78-XX)

Citations by Year