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,436 Publications (since 1997) References Indexed: 989 Publications with 25,202 References.
all top 5

Latest Issues

 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) 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) ...and 80 more Volumes
all top 5

Authors

 15 Spirakis, Paul G. 12 Fotakis, Dimitris A. 12 Lohrey, Markus 11 Scheideler, Christian 10 Diekert, Volker 10 Niedermeier, Rolf 9 Anshelevich, Elliot 9 Cai, Jin-Yi 9 Caragiannis, Ioannis 9 Kaklamanis, Christos 9 Mayordomo, Elvira 9 Saurabh, Saket 9 Watanabe, Osamu 8 Bilò, Vittorio 8 Bollig, Beate 8 Buhrman, Harry 8 Epstein, Leah 8 Fomin, Fedor V. 8 Hitchcock, John M. 8 Meyer auf der Heide, Friedhelm 8 Patt-Shamir, Boaz 7 Allender, Eric W. 7 Bergstra, Jan A. 7 Bodlaender, Hans L. 7 Carton, Olivier 7 Golovach, Petr A. 7 Krizanc, Danny 7 Luccio, Fabrizio 7 Mavronicolas, Marios 7 Merkle, Wolfgang 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 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 Hansen, Kristoffer Arnsfelt 5 Langerman, Stefan 5 Mahajan, Meena 5 Markakis, Evangelos 5 Muscholl, Anca 5 Nikoletseas, Sotiris E. 5 Ogihara, Mitsunori 5 Okhotin, Alexander 5 Pavan, Aduri 5 Persiano, Giuseppe 5 Pilipczuk, Marcin L. 5 Pucci, Geppino 5 Rosamond, Frances A. 5 Rossmanith, Peter 5 Rothe, Jörg-Matthias 5 Serna Iglesias, Maria José 5 Stephan, Frank 4 Adler, Micah 4 Albers, Susanne 4 Arvind, Vikraman 4 Barceló, Pablo 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 Fischer, Felix 4 Flocchini, Paola 4 Freydenberger, Dominik D. 4 Geerts, Floris 4 Guo, Jiong 4 Gutin, Gregory Z. 4 Harks, Tobias 4 Hirsch, Edward A. 4 Hoyrup, Mathieu 4 Jansen, Klaus ...and 2,212 more Authors
all top 5

Fields

 1,264 Computer science (68-XX) 192 Combinatorics (05-XX) 158 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 149 Mathematical logic and foundations (03-XX) 122 Operations research, mathematical programming (90-XX) 94 General and overarching topics; collections (00-XX) 39 Information and communication theory, circuits (94-XX) 27 Group theory and generalizations (20-XX) 21 Dynamical systems and ergodic theory (37-XX) 19 Number theory (11-XX) 11 Quantum theory (81-XX) 10 Probability theory and stochastic processes (60-XX) 8 Measure and integration (28-XX) 8 Statistics (62-XX) 7 Order, lattices, ordered algebraic structures (06-XX) 7 Linear and multilinear algebra; matrix theory (15-XX) 7 Biology and other natural sciences (92-XX) 6 Numerical analysis (65-XX) 5 Convex and discrete geometry (52-XX) 5 General topology (54-XX) 4 General algebraic systems (08-XX) 4 Real functions (26-XX) 3 Algebraic geometry (14-XX) 3 Functions of a complex variable (30-XX) 2 History and biography (01-XX) 2 Associative rings and algebras (16-XX) 1 Commutative algebra (13-XX) 1 Ordinary differential equations (34-XX) 1 Partial differential equations (35-XX) 1 Harmonic analysis on Euclidean spaces (42-XX) 1 Functional analysis (46-XX) 1 Operator theory (47-XX) 1 Differential geometry (53-XX) 1 Mechanics of particles and systems (70-XX) 1 Statistical mechanics, structure of matter (82-XX) 1 Systems theory; control (93-XX)

Citations contained in zbMATH Open

953 Publications have been cited 5,330 times in 4,493 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.
2000
Polynomial closure and unambiguous product. Zbl 0872.68119
Pin, J.-E.; Weil, P.
1997
Compressed suffix trees with full functionality. Zbl 1148.68015
2007
Graph-modeled data clustering: Exact algorithms for clique generation. Zbl 1084.68117
Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf
2005
On covering problems of codes. Zbl 0868.94056
Frances, M.; Litman, A.
1997
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
2008
Upper and lower bounds for randomized search heuristics in black-box optimization. Zbl 1103.68115
Droste, Stefan; Jansen, Thomas; Wegener, Ingo
2006
Network design with weighted players. Zbl 1176.91003
Chen, Ho-Lin; Roughgarden, Tim
2009
Finite presentations of infinite structures: Automata and interpretations. Zbl 1061.03038
Blumensath, Achim; Grädel, Erich
2004
Numeration systems on a regular language. Zbl 0969.68095
Lecomte, P. B. A.; Rigo, M.
2001
Fixed-parameter algorithms for cluster vertex deletion. Zbl 1205.68263
Hüffner, Falk; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf
2010
Gradient clock synchronization in dynamic networks. Zbl 1253.68060
Kuhn, Fabian; Locher, Thomas; Oshman, Rotem
2011
Approximate equilibria and ball fusion. Zbl 1101.68336
Koutsoupias, Elias; Mavronicolas, Marios; Spirakis, Paul
2003
Applying modular decomposition to parameterized cluster editing problems. Zbl 1179.68111
Protti, Fábio; Dantas da Silva, Maise; Szwarcfiter, Jayme Luiz
2009
Crown structures for vertex cover kernelization. Zbl 1148.68035
Abu-Khzam, Faisal N.; Fellows, Michael R.; Langston, Michael A.; Suters, W. Henry
2007
Generating shorter bases for hard random lattices. Zbl 1217.94092
Alwen, Joël; Peikert, Chris
2011
Nearest common ancestors: a survey and a new algorithm for a distributed environment. Zbl 1093.68136
Alstrup, Stephen; Gavoille, Cyril; Kaplan, Haim; Rauhe, Theis
2004
On edge irregular total labeling of categorical product of two cycles. Zbl 1284.05232
2014
Balanced graph partitioning. Zbl 1113.68069
Andreev, Konstantin; Räcke, Harald
2006
A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Zbl 0896.68080
Staiger, L.
1998
Exact complexity of the winner problem for Young elections. Zbl 1061.90084
Rothe, Jörg; Spakowski, Holger; Vogel, Jörg
2003
Undecidable problems for probabilistic automata of fixed dimension. Zbl 1039.68061
Blondel, Vincent D.; Canterini, Vincent
2003
Clique-width for 4-vertex forbidden subgraphs. Zbl 1103.68088
Brandstädt, Andreas; Engelfriet, Joost; Le, Hoang-Oanh; Lozin, Vadim V.
2006
Complexity of Presburger arithmetic with fixed quantifier dimension. Zbl 0872.68048
Schöning, U.
1997
Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327
Jeż, Artur; Okhotin, Alexander
2010
Algebraic results on quantum automata. Zbl 1101.68029
Ambainis, Andris; Beaudry, Martin; Golovkins, Marats; Kikusts, Arnolds; Mercer, Mark; Therien, Denis
2006
Irregular total labellings of generalized Petersen graphs. Zbl 1254.05172
Haque, Khandoker Mohammed Mominul
2012
Equational elements in additive algebras. Zbl 0914.68118
Bozapalidis, S.
1999
On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109
Berman, P.; Fujito, T.
1999
Accessing nearby copies of replicated objects in a distributed environment. Zbl 0929.68126
Plaxton, C. G.; Rajaraman, R.; Richa, A. W.
1999
Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter. Zbl 1286.68196
Jansen, Bart M. P.; Bodlaender, Hans L.
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
2009
Parameterized complexity of Vertex Cover variants. Zbl 1147.68607
Guo, Jiong; Niedermeier, Rolf; Wernicke, Sebastian
2007
The power of commuting with finite sets of words. Zbl 1121.68065
Kunc, Michal
2007
Fixed points, Nash equilibria, and the existential theory of the reals. Zbl 1362.68088
Schaefer, Marcus; Štefankovič, Daniel
2017
A generalization of Cobham’s theorem. Zbl 0895.68081
Durand, F.
1998
The efficiency of fair division. Zbl 1262.91099
Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria
2012
New graph classes of bounded clique-width. Zbl 1084.68088
Brandstädt, Andreas; Dragan, Feodor F.; Le, Hoàng-Oanh; Mosca, Raffaele
2005
The hub number of Sierpiński-like graphs. Zbl 1234.05178
Lin, Chien-Hung; Liu, Jia-Jie; Wang, Yue-Li; Yen, William Chung-Kung
2011
Local MST computation with short advice. Zbl 1213.68123
Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle
2010
Descendants of primitive substitutions. Zbl 0916.68086
Holton, C.; Zamboni, L. Q.
1999
A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192
Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin
2016
Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Zbl 1148.68041
Mölle, Daniel; Richter, Stefan; Rossmanith, Peter
2008
Efficient exact algorithms through enumerating maximal independent sets and other techniques. Zbl 1148.68054
Raman, Venkatesh; Saurabh, Saket; Sikdar, Somnath
2007
Correspondence principles for effective dimensions. Zbl 1084.68054
Hitchcock, John M.
2005
Randomness on computable probability spaces – a dynamical point of view. Zbl 1238.68069
Gács, Peter; Hoyrup, Mathieu; Rojas, Cristóbal
2011
DNA computing based on splicing: The existence of universal computers. Zbl 0914.68072
Freund, R.; Kari, L.; Păun, Gh.
1999
From a zoo to a zoology: Towards a general theory of graph polynomials. Zbl 1162.68502
Makowsky, J. A.
2008
Constant thresholds can make target set selection tractable. Zbl 1319.68109
Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias
2014
The linear arrangement problem parameterized above guaranteed value. Zbl 1148.68039
Gutin, Gregory; Rafiey, Arash; Szeider, Stefan; Yeo, Anders
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
2007
On approximate jumbled pattern matching in strings. Zbl 1253.68372
Burcsi, Péter; Cicalese, Ferdinando; Fici, Gabriele; Lipták, Zsuzsanna
2012
Simple and improved parameterized algorithms for multiterminal cuts. Zbl 1213.68472
Xiao, Mingyu
2010
A cubic kernel for feedback vertex set and loop cutset. Zbl 1215.68170
Bodlaender, Hans L.; van Dijk, Thomas C.
2010
On the uniform computational content of computability theory. Zbl 1420.03110
Brattka, Vasco; Hendtlass, Matthew; Kreuzer, Alexander P.
2017
Dynamic programming for minimum Steiner trees. Zbl 1148.68038
Fuchs, B.; Kern, W.; Molle, D.; Richter, S.; Rossmanith, P.; Wang, X.
2007
Sofic tree-shifts. Zbl 1293.68195
Aubrun, Nathalie; Béal, Marie-Pierre
2013
Fault-tolerant embedding of pairwise independent Hamiltonian paths on a faulty hypercube with edge faults. Zbl 1187.68344
Hsieh, Sun-Yuan; Weng, Yu-Fen
2009
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.
2012
First- and second-order diffusive methods for rapid, coarse, distributed load balancing. Zbl 0904.68137
Muthukrishnan, S.; Ghosh, B.; Schultz, M. H.
1998
Nash equilibria and the price of anarchy for flows over time. Zbl 1278.91027
Koch, Ronald; Skutella, Martin
2011
Complexity of equations over sets of natural numbers. Zbl 1209.68263
Jeż, Artur; Okhotin, Alexander
2011
The rank-width of edge-coloured graphs. Zbl 1269.05036
2013
Distributed streams algorithms for sliding windows. Zbl 1093.68143
Gibbons, Phillip B.; Tirthapura, Srikanta
2004
A Kleene theorem for weighted tree automata. Zbl 1061.68092
Droste, Manfred; Pech, Christian; Vogler, Heiko
2005
Stackelberg strategies for atomic congestion games. Zbl 1203.91035
Fotakis, Dimitris
2010
The complexity of equality constraint languages. Zbl 1148.68025
Bodirsky, Manuel; Kára, Jan
2008
Computational complexity of certain problems related to carefully synchronizing words for partial automata and directing words for nondeterministic automata. Zbl 1380.68257
Martyugin, Pavel
2014
$$\frac{13}{9}$$-approximation for graphic TSP. Zbl 1319.68255
Mucha, Marcin
2014
The hardness of approximating spanner problems. Zbl 1148.68024
Elkin, Michael; Peleg, David
2007
Space efficient hash tables with worst case constant access time. Zbl 1066.68025
Fotakis, Dimitris; Pagh, Rasmus; Sanders, Peter; Spirakis, Paul
2005
Stackelberg strategies and collusion in network games with splittable flow. Zbl 1213.91043
Harks, Tobias
2011
Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications. Zbl 1175.90366
Tsaggouris, George; Zaroliagis, Christos
2009
Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022
Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola
2007
Real hypercomputation and continuity. Zbl 1122.03039
Ziegler, Martin
2007
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.
2010
Solving the 2-disjoint paths problem in nearly linear time. Zbl 1103.68100
Tholey, Torsten
2006
Thread scheduling for multiprogrammed multiprocessors. Zbl 0978.68020
Arora, N. S.; Blumofe, R. D.; Plaxton, C. G.
2001
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
1997
Greedy numeration systems and regularity. Zbl 0895.68088
Hollander, Michael Israel
1998
Lower bounds for kernelizations and other preprocessing procedures. Zbl 1234.68118
Chen, Yijia; Flum, Jörg; Müller, Moritz
2011
Characterizing the existence of potential functions in weighted congestion games. Zbl 1278.91013
Harks, Tobias; Klimm, Max; Möhring, Rolf H.
2011
Trimmed Moebius inversion and graphs of bounded degree. Zbl 1225.05005
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko
2010
Vertex cover problem parameterized above and below tight bounds. Zbl 1209.68276
Gutin, Gregory; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia
2011
Weighted logics for unranked tree automata. Zbl 1226.03048
Droste, Manfred; Vogler, Heiko
2011
Analysis of approximation algorithms for $$k$$-set cover using factor-revealing linear programs. Zbl 1170.90461
Athanassopoulos, Stavros; Caragiannis, Ioannis; Kaklamanis, Christos
2009
Fixed-parameter enumerability of cluster editing and related problems. Zbl 1209.68360
Damaschke, Peter
2010
The complexity of optimal design of temporally connected graphs. Zbl 1379.68250
Akrida, Eleni C.; Gąsieniec, Leszek; Mertzios, George B.; Spirakis, Paul G.
2017
Hamiltonicity of the hierarchical cubic network. Zbl 0993.68003
Fu, Jung-Sheng; Chen, Gen-Huey
2002
The mortality problem for matrices of low dimensions. Zbl 1016.68038
Bournez, O.; Branicky, M.
2002
Planar and grid graph reachability problems. Zbl 1183.68409
Allender, Eric; Mix Barrington, David A.; Chakraborty, Tanmoy; Datta, Samir; Roy, Sambuddha
2009
Regular languages and Stone duality. Zbl 0870.68092
Pippenger, N.
1997
Weak MSO with the unbounding quantifier. Zbl 1227.03051
Bojańczyk, Mikołaj
2011
Weighted picture automata and weighted logics. Zbl 1229.03035
Fichtner, Ina
2011
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.
1998
Bounding the expected length of longest common subsequences and forests. Zbl 0934.68043
Baeza-Yates, R. A.; Gavaldá, R.; Navarro, G.; Scheihing, R.
1999
Symbolic dynamics: entropy = dimension = complexity. Zbl 1355.37023
Simpson, Stephen G.
2015
Online removable square packing. Zbl 1135.90434
Han, Xin; Iwama, Kazuo; Zhang, Guochuan
2008
Exact algorithms for graph homomorphisms. Zbl 1119.68133
Fomin, Fedor V.; Heggernes, Pinar; Kratsch, Dieter
2007
The bell is ringing in speed-scaled multiprocessor scheduling. Zbl 1310.68048
Greiner, Gero; Nonner, Tim; Souza, Alexander
2014
Multistage vertex cover. Zbl 07523542
Fluschnik, Till; Niedermeier, Rolf; Rohm, Valentin; Zschoche, Philipp
2022
Token sliding on split graphs. Zbl 07379111
Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian
2021
The containment problem for unambiguous register automata and unambiguous timed automata. Zbl 07379113
Mottet, Antoine; Quaas, Karin
2021
Finite sequentiality of unambiguous max-plus tree automata. Zbl 07379114
Paul, Erik
2021
On triangle estimation using tripartite independent set queries. Zbl 07449499
Bhattacharya, Anup; Bishnu, Arijit; Ghosh, Arijit; Mishra, Gopinath
2021
Semi-oblivious chase termination: the sticky case. Zbl 1477.68088
Calautti, Marco; Pieris, Andreas
2021
Consistent query answering for primary keys in Datalog. Zbl 1477.68091
Koutris, Paraschos; Wijsen, Jef
2021
Fast scheduling in distributed transactional memory. Zbl 1464.68036
Busch, Costas; Herlihy, Maurice; Popovic, Miroslav; Sharma, Gokarna
2021
Faster parameterized algorithm for cluster vertex deletion. Zbl 07363125
Tsur, Dekel
2021
Computability of products of chainable continua. Zbl 07363127
Čelar, Matea; Iljazović, Zvonko
2021
Stable divisorial gonality is in NP. Zbl 1477.68204
Bodlaender, Hans L.; van der Wegen, Marieke; van der Zanden, Tom C.
2021
The non-hardness of approximating circuit size. Zbl 07377743
Allender, Eric; Ilango, Rahul; Vafa, Neekon
2021
Forward looking Huffman coding. Zbl 07377745
Klein, Shmuel T.; Saadia, Shoham; Shapira, Dana
2021
On tseitin formulas, read-once branching programs and treewidth. Zbl 07377746
Glinskih, Ludmila; Itsykson, Dmitry
2021
Constructing antidictionaries of long texts in output-sensitive space. Zbl 07379115
Ayad, Lorraine A. K.; Badkobeh, Golnaz; Fici, Gabriele; Héliou, Alice; Pissis, Solon P.
2021
Streaming algorithms for bin packing and vector scheduling. Zbl 07402287
Cormode, Graham; Veselý, Pavel
2021
The price of fairness for indivisible goods. Zbl 1471.91196
Bei, Xiaohui; Lu, Xinhang; Manurangsi, Pasin; Suksompong, Warut
2021
Additive number theory via automata theory. Zbl 1475.11040
Rajasekaran, Aayush; Shallit, Jeffrey; Smith, Tim
2020
Fast algorithms for the shortest unique palindromic substring problem on run-length encoded strings. Zbl 07357723
Watanabe, Kiichi; Nakashima, Yuto; Inenaga, Shunsuke; Bannai, Hideo; Takeda, Masayuki
2020
Computing hitting set kernels by $$\mathrm{AC}^0$$-circuits. Zbl 1433.68177
Bannach, Max; Tantau, Till
2020
Lower bound techniques for QBF expansion. Zbl 1471.03081
2020
Optimal dislocation with persistent errors in subquadratic time. Zbl 1433.68111
Geissmann, Barbara; Leucci, Stefano; Liu, Chih-Hung; Penna, Paolo
2020
Conflict free version of covering problems on graphs: classical and parameterized. Zbl 1453.68136
Jain, Pallavi; Kanesh, Lawqueen; Misra, Pranabendu
2020
Multiplication algorithm based on Collatz function. Zbl 1462.11112
Barina, David
2020
Recognizing read-once functions from depth-three formulas. Zbl 1434.68201
Kozachinskiy, Alexander
2020
Slopes of multidimensional subshifts. Zbl 1440.37025
Jeandel, Emmanuel; Moutot, Etienne; Vanier, Pascal
2020
Complexity and inapproximability results for parallel task scheduling and strip packing. Zbl 1477.68119
Henning, Sören; Jansen, Klaus; Rau, Malin; Schmarje, Lars
2020
New bounds for truthful scheduling on two unrelated selfish machines. Zbl 1434.68678
Kuryatnikova, Olga; Vera, Juan C.
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.
2020
On the tree conjecture for the network creation game. Zbl 1443.91071
Bilò, Davide; Lenzner, Pascal
2020
Effective categoricity of automatic equivalence and nested equivalence structures. Zbl 1485.03109
Carson, Jacob; Cenzer, Douglas; Remmel, Jeffrey B.
2020
Parameterized complexity of min-power asymmetric connectivity. Zbl 07357718
Bentert, Matthias; Haag, Roman; Hofer, Christian; Koana, Tomohiro; Nichterlein, André
2020
Dichotomy for Holant$$^\ast$$ problems on the Boolean domain. Zbl 07357729
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji
2020
Deterministic min-cost matching with delays. Zbl 1444.68297
Azar, Yossi; Jacob Fanani, Amit
2020
On the stab number of rectangle intersection graphs. Zbl 1442.05187
Chakraborty, Dibyayan; Francis, Mathew C.
2020
On limitations of structured (deterministic) DNNFs. Zbl 1446.68152
Bollig, Beate; Buttkus, Matthias
2020
Distribution policies for Datalog. Zbl 1446.68057
Ketsman, Bas; Albarghouthi, Aws; Koutris, Paraschos
2020
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
2019
Comparing linear width parameters for directed graphs. Zbl 1420.05068
Gurski, Frank; Rehs, Carolin
2019
Verification of quantum computation: an overview of existing approaches. Zbl 1423.68281
Gheorghiu, Alexandru; Kapourniotis, Theodoros; Kashefi, Elham
2019
Generic results for concatenation hierarchies. Zbl 1423.68264
Place, Thomas; Zeitoun, Marc
2019
On the relative succinctness of sentential decision diagrams. Zbl 1435.68320
Bollig, Beate; Buttkus, Matthias
2019
The real computational complexity of minmax value and equilibrium refinements in multi-player games. Zbl 1422.91046
Hansen, Kristoffer Arnsfelt
2019
The operator approach to entropy games. Zbl 1422.91080
Akian, Marianne; Gaubert, Stéphane; Grand-Clément, Julien; Guillaud, Jérémie
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
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
2019
On-line path computation and function placement in SDNs. Zbl 1423.68046
Even, Guy; Medina, Moti; Patt-Shamir, Boaz
2019
On the parameterized complexity of contraction to generalization of trees. Zbl 1435.68119
Agarwal, Akanksha; Saurabh, Saket; Tale, Prafullkumar
2019
The descriptive complexity of subgraph isomorphism without numerics. Zbl 1435.68114
Verbitsky, Oleg; Zhukovskii, Maksim
2019
On Stackelberg strategies in affine congestion games. Zbl 1422.91143
Bilò, Vittorio; Vinci, Cosimo
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.
2019
A logic for document spanners. Zbl 1430.68081
Freydenberger, Dominik D.
2019
On conceptually simple algorithms for variants of online bipartite matching. Zbl 1429.91230
Borodin, Allan; Pankratov, Denis; Salehi-Abari, Amirali
2019
Designing cost-sharing methods for Bayesian games. Zbl 1409.91147
Christodoulou, George; Leonardi, Stefano; Sgouritsa, Alkmini
2019
Price of anarchy for highly congested routing games in parallel networks. Zbl 1411.91136
Colini-Baldeschi, Riccardo; Cominetti, Roberto; Scarsini, Marco
2019
An almost ideal coordination mechanism for unrelated machine scheduling. Zbl 1411.90108
Caragiannis, Ioannis; Fanelli, Angelo
2019
The stable roommates problem with short lists. Zbl 1418.91387
Cseh, Ágnes; Irving, Robert W.; Manlove, David F.
2019
Synchronous gathering without multiplicity detection: a certified algorithm. Zbl 1423.68522
Balabonski, Thibaut; Delga, Amélie; Rieg, Lionel; Tixeuil, Sébastien; Urbain, Xavier
2019
Wait-free solvability of colorless tasks in anonymous shared-memory model. Zbl 1423.68079
Yanagisawa, Nayuta
2019
Pattern matching and consensus problems on weighted sequences and profiles. Zbl 1423.68620
Kociumaka, Tomasz; Pissis, Solon P.; Radoszewski, Jakub
2019
Algorithmic randomness and Fourier analysis. Zbl 1454.03054
Franklin, Johanna N. Y.; McNicholl, Timothy H.; Rute, Jason
2019
A unifying approach to algebraic systems over semirings. Zbl 1431.68067
Kostolányi, Peter
2019
Unary coded PSPACE-complete languages in $$\mathrm{ASPACE}(\log\log n)$$. Zbl 1425.68199
Geffert, Viliam
2019
Bounds on the bend number of split and cocomparability graphs. Zbl 1420.05120
Chakraborty, Dibyayan; Das, Sandip; Mukherjee, Joydeep; Sahoo, Uma Kant
2019
Tight welfare guarantees for pure Nash equilibria of the uniform price auction. Zbl 1422.91294
Birmpas, Georgios; Markakis, Evangelos; Telelis, Orestis; Tsikiridis, Artem
2019
Online random sampling for budgeted settings. Zbl 1422.91301
Eden, Alon; Feldman, Michal; Vardi, Adi
2019
Better streaming algorithms for the maximum coverage problem. Zbl 1421.90128
McGregor, Andrew; Vu, Hoa T.
2019
Complete semialgebraic invariant synthesis for the Kannan-Lipton orbit problem. Zbl 1461.37028
Fijalkow, Nathanaël; Ohlmann, Pierre; Ouaknine, Joël; Pouly, Amaury; Worrell, James
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
2018
Co-c.e. sets with disconnected complements. Zbl 1436.03231
Iljazović, Zvonko; Pažek, Bojan
2018
A unifying tool for bounding the quality of non-cooperative solutions in weighted congestion games. Zbl 1394.91015
Bilò, Vittorio
2018
Knapsack in graph groups. Zbl 1386.68073
Lohrey, Markus; Zetzsche, Georg
2018
Exploration of the $$T$$-interval-connected dynamic graphs: the case of the ring. Zbl 1392.68099
2018
A randomized polynomial kernel for subset feedback vertex set. Zbl 1387.68134
Hols, Eva-Maria C.; Kratsch, Stefan
2018
Space efficient linear time algorithms for BFS, DFS and applications. Zbl 1430.68173
Banerjee, Niranka; Chakraborty, Sankardeep; Raman, Venkatesh; Satti, Srinivasa Rao
2018
Polynomial kernels for vertex cover parameterized by small degree modulators. Zbl 1419.05179
Majumdar, Diptapriyo; Raman, Venkatesh; Saurabh, Saket
2018
Improved approximation algorithms for minimum cost node-connectivity augmentation problems. Zbl 1394.68443
Nutov, Zeev
2018
Collaborative exploration of trees by energy-constrained mobile robots. Zbl 1392.68412
Das, Shantanu; Dereniowski, Dariusz; Karousatou, Christina
2018
Faster algorithms for the constrained $$k$$-means problem. Zbl 1387.68296
Bhattacharya, Anup; Jaiswal, Ragesh; Kumar, Amit
2018
Finite-state independence. Zbl 1404.68066
Becher, Verónica; Carton, Olivier; Heiber, Pablo Ariel
2018
Comparing representations for function spaces in computable analysis. Zbl 1436.03241
Pauly, Arno; Steinberg, Florian
2018
Parameterizing edge modification problems above lower bounds. Zbl 1386.68075
van Bevern, René; Froese, Vincent; Komusiewicz, Christian
2018
Finding cactus roots in polynomial time. Zbl 1391.68052
Golovach, Petr A.; Kratsch, Dieter; Paulusma, Daniël; Stewart, Anthony
2018
Effective Hausdorff dimension in general metric spaces. Zbl 1436.03232
Mayordomo, Elvira
2018
Level two of the quantifier alternation hierarchy over infinite words. Zbl 1436.03216
Kufleitner, Manfred; Walter, Tobias
2018
Tropically convex constraint satisfaction. Zbl 1390.68333
Bodirsky, Manuel; Mamino, Marcello
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
2018
Some complete and intermediate polynomials in algebraic complexity theory. Zbl 1393.68079
Mahajan, Meena; Saurabh, Nitin
2018
The word problem for omega-terms over the Trotter-Weil hierarchy. Zbl 1435.20065
Kufleitner, Manfred; Wächter, Jan Philipp
2018
Document spanners: from expressive power to decision problems. Zbl 1392.68167
Freydenberger, Dominik D.; Holldack, Mario
2018
Limits of schema mappings. Zbl 1392.68170
Kolaitis, Phokion G.; Pichler, Reinhard; Sallinger, Emanuel; Savenkov, Vadim
2018
The complexity of tensor rank. Zbl 1396.68061
Schaefer, Marcus; Štefankovič, Daniel
2018
Syntactic complexity of regular ideals. Zbl 1398.68301
Brzozowski, Janusz A.; Szykuła, Marek; Ye, Yuli
2018
On effective Birkhoff’s ergodic theorem for computable actions of amenable groups. Zbl 1436.03234
Moriakov, Nikita
2018
Homonym population protocols. Zbl 1392.68095
Bournez, Olivier; Cohen, Johanne; Rabie, Mikaël
2018
Minimax regret 1-median problem in dynamic path networks. Zbl 1397.90236
Higashikawa, Yuya; Cheng, Siu-Wing; Kameda, Tsunehiko; Katoh, Naoki; Saburi, Shun
2018
Partial covering arrays: algorithms and asymptotics. Zbl 1391.68085
Sarkar, Kaushik; Colbourn, Charles J.; De Bonis, Annalisa; Vaccaro, Ugo
2018
Covering triangles in edge-weighted graphs. Zbl 1396.05090
Chen, Xujin; Diao, Zhuo; Hu, Xiaodong; Tang, Zhongzheng
2018
Testing shape restrictions of discrete distributions. Zbl 1386.68215
Canonne, Clément L.; Diakonikolas, Ilias; Gouleakis, Themis; Rubinfeld, Ronitt
2018
Catalytic space: non-determinism and hierarchy. Zbl 1387.68109
Buhrman, Harry; Koucký, Michal; Loff, Bruno; Speelman, Florian
2018
...and 853 more Documents
all top 5

Cited by 5,821 Authors

 42 Saurabh, Saket 38 Niedermeier, Rolf 31 Fomin, Fedor V. 31 Lozin, Vadim Vladislavovich 30 Golovach, Petr A. 29 Paulusma, Daniël 28 Okhotin, Alexander 27 Lohrey, Markus 25 Epstein, Leah 23 Courcelle, Bruno 23 Ganian, Robert 23 Stephan, Frank 22 Lokshtanov, Daniel 22 Rigo, Michel 21 Heggernes, Pinar 20 Bilò, Vittorio 20 Fellows, Michael Ralph 20 Hemaspaandra, Lane A. 20 Kratsch, Dieter 20 Navarro, Gonzalo 19 Bazgan, Cristina 19 Komusiewicz, Christian 19 Kratsch, Stefan 19 Mitrana, Victor 19 Raman, Venkatesh 19 Spirakis, Paul G. 18 Bodlaender, Hans L. 18 Brandstädt, Andreas 18 Fernau, Henning 18 Guo, Jiong 18 Pilipczuk, Michał 18 Vogler, Heiko 17 Chen, Jian-er 17 Gurski, Frank 17 Milanič, Martin 17 Pelc, Andrzej 17 Rothe, Jörg-Matthias 17 Santoro, Nicola 16 Caragiannis, Ioannis 16 Dabrowski, Konrad Kazimierz 16 Flocchini, Paola 16 Gutin, Gregory Z. 16 Jansen, Bart M. P. 15 Bača, Martin 15 Harks, Tobias 15 Jain, Sanjay 15 Lampis, Michael 14 Brattka, Vasco 14 Chang, Chih-Hung 14 Doerr, Benjamin 14 Downey, Rodney Graham 14 Droste, Manfred 14 Fülöp, Zoltán 14 Korman, Amos 14 Kwon, Ojoung 14 Maletti, Andreas 14 Mavronicolas, Marios 14 Monnot, Jérôme 14 Paschos, Vangelis Th. 14 Rossmanith, Peter 13 Ban, Jungchao 13 Bergstra, Jan A. 13 Blanchet-Sadri, Francine 13 Dell, Holger 13 Diekert, Volker 13 Fraigniaud, Pierre 13 Hitchcock, John M. 13 Kowalski, Dariusz R. 13 Levin, Asaf 13 Manea, Florin 13 Mnich, Matthias 13 Otachi, Yota 13 Pilipczuk, Marcin L. 13 Protti, Fábio 13 Suchý, Ondřej 13 Szeider, Stefan 13 Zamaraev, Victor A. 13 Zehavi, Meirav 12 Bodirsky, Manuel 12 Carton, Olivier 12 Hemaspaandra, Edith 12 Jeż, Artur 12 Kaklamanis, Christos 12 Kufleitner, Manfred 12 Lutz, Jack H. 12 Nichterlein, André 12 Papadopoulos, Charis 12 Pauly, Arno M. 12 Rautenbach, Dieter 12 Semaničová-Feňovčíková, Andrea 12 Wang, Jianxin 11 Böckenhauer, Hans-Joachim 11 Bollig, Beate 11 Busch, Costas 11 Cai, Jin-Yi 11 Censor-Hillel, Keren 11 Charlier, Emilie 11 Gaspers, Serge 11 Glaßer, Christian 11 Han, Xin ...and 5,721 more Authors
all top 5

Cited in 354 Journals

 687 Theoretical Computer Science 255 Algorithmica 253 Theory of Computing Systems 200 Discrete Applied Mathematics 164 Journal of Computer and System Sciences 150 Information and Computation 140 Information Processing Letters 75 Distributed Computing 73 Journal of Combinatorial Optimization 71 International Journal of Foundations of Computer Science 57 SIAM Journal on Computing 43 Discrete Mathematics 43 SIAM Journal on Discrete Mathematics 43 Journal of Discrete Algorithms 38 Logical Methods in Computer Science 31 Annals of Pure and Applied Logic 28 European Journal of Operational Research 28 RAIRO. Theoretical Informatics and Applications 26 Information Sciences 25 Acta Informatica 25 Artificial Intelligence 22 Mathematics of Operations Research 22 Computational Geometry 22 Computational Complexity 21 The Journal of Symbolic Logic 21 Computers & Operations Research 20 International Journal of Algebra and Computation 20 Discrete Optimization 17 Games and Economic Behavior 17 Computer Science Review 16 European Journal of Combinatorics 16 Mathematical Programming. Series A. Series B 16 Journal of Scheduling 15 Operations Research Letters 15 Journal of Parallel and Distributed Computing 14 Optimization Letters 14 Algorithms 13 Applied Mathematics and Computation 13 RAIRO. Theoretical Informatics and Applications 12 Journal of Combinatorial Theory. Series B 12 Operations Research 12 Annals of Mathematics and Artificial Intelligence 11 Journal of Algebra 11 Annals of Operations Research 11 MSCS. Mathematical Structures in Computer Science 11 The Electronic Journal of Combinatorics 11 Natural Computing 11 ACM Transactions on Computational Logic 10 Journal of the ACM 9 Journal of Graph Theory 9 Transactions of the American Mathematical Society 9 Journal of Global Optimization 9 International Journal of Computer Mathematics 9 Mathematics in Computer Science 9 Discrete Mathematics, Algorithms and Applications 8 Networks 8 Advances in Applied Mathematics 8 Ergodic Theory and Dynamical Systems 8 Discrete & Computational Geometry 8 International Journal of Computational Geometry & Applications 8 Linear Algebra and its Applications 8 Mathematical Logic Quarterly (MLQ) 8 The Journal of Artificial Intelligence Research (JAIR) 8 Journal of Applied Logic 7 Journal of Statistical Physics 7 Journal of Combinatorial Theory. Series A 7 Proceedings of the American Mathematical Society 7 Journal of Automated Reasoning 7 Journal of Applied Non-Classical Logics 7 Journal of Graph Algorithms and Applications 7 AKCE International Journal of Graphs and Combinatorics 7 Computability 6 International Journal of Game Theory 6 Graphs and Combinatorics 6 Journal of Complexity 6 International Journal of Approximate Reasoning 6 Random Structures & Algorithms 6 Archive for Mathematical Logic 6 The Bulletin of Symbolic Logic 6 Journal of Automata, Languages and Combinatorics 6 ACM Journal of Experimental Algorithmics 5 International Journal of Theoretical Physics 5 Algebra and Logic 5 Algebra Universalis 5 Annales de l’Institut Fourier 5 Automatica 5 Fuzzy Sets and Systems 5 Semigroup Forum 5 Topology and its Applications 5 Designs, Codes and Cryptography 5 Automation and Remote Control 5 Formal Methods in System Design 5 International Transactions in Operational Research 5 Discrete Mathematics and Theoretical Computer Science. DMTCS 5 Journal of Mathematical Logic 5 Fundamenta Informaticae 5 Lobachevskii Journal of Mathematics 5 Internet Mathematics 5 AIMS Mathematics 5 Prikladnaya Diskretnaya Matematika ...and 254 more Journals
all top 5

Cited in 51 Fields

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