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,547 Publications (since 1997) References Indexed: 1,093 Publications with 28,493 References. all top 5 Latest Issues 68, No. 5 (2024) 68, No. 4 (2024) 68, No. 3 (2024) 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) ...and 93 more Volumes all top 5 Authors 15 Spirakis, Paul G. 14 Lohrey, Markus 12 Fotakis, Dimitris A. 11 Diekert, Volker 11 Mayordomo, Elvira 11 Saurabh, Saket 11 Scheideler, Christian 10 Cai, Jin-Yi 10 Caragiannis, Ioannis 10 Niedermeier, Rolf 9 Anshelevich, Elliot 9 Fomin, Fedor V. 9 Kaklamanis, Christos 9 Patt-Shamir, Boaz 9 Watanabe, Osamu 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 Okhotin, Alexander 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 McNicholl, Timothy H. 6 Rosenberg, Arnold Leonard 6 Rothe, Jörg-Matthias 6 Schwentick, Thomas 6 Vereshchagin, Nikolay K. 6 Vollmer, Heribert 6 Weiß, Armin 5 Antunes, Luis 5 Azar, Yossi 5 Bienvenu, Laurent 5 Bläser, Markus 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 Kulikov, Alexander S. 5 Langerman, Stefan 5 Litman, Ami 5 Mahajan, Meena 5 Manea, Florin 5 Markakis, Evangelos 5 Middelburg, Cornelis A. 5 Muscholl, Anca 5 Nikoletseas, Sotiris E. 5 Pavan, Aduri 5 Persiano, Giuseppe 5 Pilipczuk, Marcin L. 5 Pilipczuk, Michał 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 Attiya, Hagit 4 Barceló, Pablo 4 Bille, Philip 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 ...and 2,368 more Authors all top 5 Fields 1,354 Computer science (68-XX) 223 Combinatorics (05-XX) 169 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 162 Mathematical logic and foundations (03-XX) 134 Operations research, mathematical programming (90-XX) 101 General and overarching topics; collections (00-XX) 46 Information and communication theory, circuits (94-XX) 31 Group theory and generalizations (20-XX) 26 Dynamical systems and ergodic theory (37-XX) 21 Number theory (11-XX) 13 Quantum theory (81-XX) 12 Order, lattices, ordered algebraic structures (06-XX) 11 Linear and multilinear algebra; matrix theory (15-XX) 9 Measure and integration (28-XX) 9 Statistics (62-XX) 9 Biology and other natural sciences (92-XX) 8 Convex and discrete geometry (52-XX) 8 Probability theory and stochastic processes (60-XX) 8 Numerical analysis (65-XX) 6 General algebraic systems (08-XX) 5 Algebraic geometry (14-XX) 5 General topology (54-XX) 3 History and biography (01-XX) 3 Real functions (26-XX) 3 Functions of a complex variable (30-XX) 2 Commutative algebra (13-XX) 2 Systems theory; control (93-XX) 1 Associative rings and algebras (16-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 Fluid mechanics (76-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 1,074 Publications have been cited 7,589 times in 6,274 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. 421 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 69 2007 Upper and lower bounds for randomized search heuristics in black-box optimization. Zbl 1103.68115 Droste, Stefan; Jansen, Thomas; Wegener, Ingo 64 2006 Graph-modeled data clustering: Exact algorithms for clique generation. Zbl 1084.68117 Gramm, Jens; Guo, Jiong; Hüffner, Falk; Niedermeier, Rolf 63 2005 On covering problems of codes. Zbl 0868.94056 Frances, M.; Litman, A. 60 1997 Generating shorter bases for hard random lattices. Zbl 1217.94092 Alwen, Joël; Peikert, Chris 58 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 Fixed-parameter algorithms for cluster vertex deletion. Zbl 1205.68263 Hüffner, Falk; Komusiewicz, Christian; Moser, Hannes; Niedermeier, Rolf 54 2010 Finite presentations of infinite structures: Automata and interpretations. Zbl 1061.03038 Blumensath, Achim; Grädel, Erich 52 2004 Fixed points, Nash equilibria, and the existential theory of the reals. Zbl 1362.68088 Schaefer, Marcus; Štefankovič, Daniel 51 2017 Network design with weighted players. Zbl 1176.91003 Chen, Ho-Lin; Roughgarden, Tim 46 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 43 2003 Balanced graph partitioning. Zbl 1113.68069 Andreev, Konstantin; Räcke, Harald 42 2006 Parameterized complexity of Vertex Cover variants. Zbl 1147.68607 Guo, Jiong; Niedermeier, Rolf; Wernicke, Sebastian 42 2007 The efficiency of fair division. Zbl 1262.91099 Caragiannis, Ioannis; Kaklamanis, Christos; Kanellopoulos, Panagiotis; Kyropoulou, Maria 40 2012 Numeration systems on a regular language. Zbl 0969.68095 Lecomte, P. B. A.; Rigo, M. 40 2001 On edge irregular total labeling of categorical product of two cycles. Zbl 1284.05232 Ahmad, Ali; Bača, Martin; Siddiqui, Muhammad Kamran 39 2014 Clique-width for 4-vertex forbidden subgraphs. Zbl 1103.68088 Brandstädt, Andreas; Engelfriet, Joost; Le, Hoang-Oanh; Lozin, Vadim V. 38 2006 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 A fast branching algorithm for cluster vertex deletion. Zbl 1336.68192 Boral, Anudhyan; Cygan, Marek; Kociumaka, Tomasz; Pilipczuk, Marcin 35 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 32 2003 Constant thresholds can make target set selection tractable. Zbl 1319.68109 Chopin, Morgan; Nichterlein, André; Niedermeier, Rolf; Weller, Mathias 32 2014 Vertex cover kernelization revisited. Upper and lower bounds for a refined parameter. Zbl 1286.68196 Jansen, Bart M. P.; Bodlaender, Hans L. 32 2013 Irregular total labellings of generalized Petersen graphs. Zbl 1254.05172 Haque, Khandoker Mohammed Mominul 31 2012 A tight upper bound on Kolmogorov complexity and uniformly optimal prediction. Zbl 0896.68080 Staiger, L. 31 1998 Algebraic results on quantum automata. Zbl 1101.68029 Ambainis, Andris; Beaudry, Martin; Golovkins, Marats; Kikusts, Arnolds; Mercer, Mark; Therien, Denis 30 2006 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 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 Enumerate and expand: Improved algorithms for connected vertex cover and tree cover. Zbl 1148.68041 Mölle, Daniel; Richter, Stefan; Rossmanith, Peter 29 2008 Equational elements in additive algebras. Zbl 0914.68118 Bozapalidis, S. 28 1999 Cryptographic and physical zero-knowledge proof systems for solutions of Sudoku puzzles. Zbl 1179.68055 Gradwohl, Ronen; Naor, Moni; Pinkas, Benny; Rothblum, Guy N. 27 2009 On approximation properties of the independent set problem for low degree graphs. Zbl 0916.68109 Berman, P.; Fujito, T. 27 1999 Nash equilibria and the price of anarchy for flows over time. Zbl 1278.91027 Koch, Ronald; Skutella, Martin 27 2011 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 Space efficient hash tables with worst case constant access time. Zbl 1066.68025 Fotakis, Dimitris; Pagh, Rasmus; Sanders, Peter; Spirakis, Paul 26 2005 The linear arrangement problem parameterized above guaranteed value. Zbl 1148.68039 Gutin, Gregory; Rafiey, Arash; Szeider, Stefan; Yeo, Anders 25 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 25 2007 \(\frac{13}{9}\)-approximation for graphic TSP. Zbl 1319.68255 Mucha, Marcin 25 2014 New graph classes of bounded clique-width. Zbl 1084.68088 Brandstädt, Andreas; Dragan, Feodor F.; Le, Hoàng-Oanh; Mosca, Raffaele 25 2005 Local MST computation with short advice. Zbl 1213.68123 Fraigniaud, Pierre; Korman, Amos; Lebhar, Emmanuelle 25 2010 A cubic kernel for feedback vertex set and loop cutset. Zbl 1215.68170 Bodlaender, Hans L.; van Dijk, Thomas C. 25 2010 Conjunctive grammars over a unary alphabet: Undecidability and unbounded growth. Zbl 1183.68327 Jeż, Artur; Okhotin, Alexander 25 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. 25 2017 From a zoo to a zoology: Towards a general theory of graph polynomials. Zbl 1162.68502 Makowsky, J. A. 24 2008 A generalization of Cobham’s theorem. Zbl 0895.68081 Durand, F. 24 1998 Dynamic programming for minimum Steiner trees. Zbl 1148.68038 Fuchs, B.; Kern, W.; Molle, D.; Richter, S.; Rossmanith, P.; Wang, X. 24 2007 Correspondence principles for effective dimensions. Zbl 1084.68054 Hitchcock, John M. 24 2005 The power of commuting with finite sets of words. Zbl 1121.68065 Kunc, Michal 24 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 23 2011 Quotient complexity of closed languages. Zbl 1380.68249 Brzozowski, Janusz; Jirásková, Galina; Zou, Chenglong 23 2014 Regular languages and Stone duality. Zbl 0870.68092 Pippenger, N. 22 1997 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 Simple and improved parameterized algorithms for multiterminal cuts. Zbl 1213.68472 Xiao, Mingyu 22 2010 Stackelberg strategies for atomic congestion games. Zbl 1203.91035 Fotakis, Dimitris 22 2010 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. 21 2012 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 Distributed streams algorithms for sliding windows. Zbl 1093.68143 Gibbons, Phillip B.; Tirthapura, Srikanta 21 2004 Vertex cover problem parameterized above and below tight bounds. Zbl 1209.68276 Gutin, Gregory; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia 21 2011 The behavior of clique-width under graph operations and graph transformations. Zbl 1358.05239 Gurski, Frank 21 2017 Sofic tree-shifts. Zbl 1293.68195 Aubrun, Nathalie; Béal, Marie-Pierre 21 2013 Real hypercomputation and continuity. Zbl 1122.03039 Ziegler, Martin 20 2007 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 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 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 The price of anarchy in network creation games is (mostly) constant. Zbl 1293.91031 Mihalák, Matúš; Schlegel, Jan Christoph 19 2013 Rendezvous and election of mobile agents: Impact of sense of direction. Zbl 1107.68022 Barriere, Lali; Flocchini, Paola; Fraigniaud, Pierre; Santoro, Nicola 18 2007 A Kleene theorem for weighted tree automata. Zbl 1061.68092 Droste, Manfred; Pech, Christian; Vogler, Heiko 18 2005 DNA computing based on splicing: The existence of universal computers. Zbl 0914.68072 Freund, R.; Kari, L.; Păun, Gh. 18 1999 The rank-width of edge-coloured graphs. Zbl 1269.05036 Kanté, Mamadou Moustapha; Rao, Michael 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 Weighted logics for unranked tree automata. Zbl 1226.03048 Droste, Manfred; Vogler, Heiko 18 2011 Multiobjective optimization: Improved FPTAS for shortest paths and nonlinear objectives with applications. Zbl 1175.90366 Tsaggouris, George; Zaroliagis, Christos 17 2009 The bell is ringing in speed-scaled multiprocessor scheduling. Zbl 1310.68048 Greiner, Gero; Nonner, Tim; Souza, Alexander 17 2014 Thread scheduling for multiprogrammed multiprocessors. Zbl 0978.68020 Arora, N. S.; Blumofe, R. D.; Plaxton, C. G. 17 2001 The hardness of approximating spanner problems. Zbl 1148.68024 Elkin, Michael; Peleg, David 17 2007 Gaming is a hard job, but someone has to do it! Zbl 1303.68075 Viglietta, Giovanni 17 2014 Robust polynomials and quantum algorithms. Zbl 1121.68049 Buhrman, Harry; Newman, Ilan; Rohrig, Hein; de Wolf, Ronald 17 2007 Planar and grid graph reachability problems. Zbl 1183.68409 Allender, Eric; Mix Barrington, David A.; Chakraborty, Tanmoy; Datta, Samir; Roy, Sambuddha 17 2009 On the uniform computational content of computability theory. Zbl 1420.03110 Brattka, Vasco; Hendtlass, Matthew; Kreuzer, Alexander P. 17 2017 Greedy numeration systems and regularity. Zbl 0895.68088 Hollander, Michael Israel 16 1998 Selfish routing with incomplete information. Zbl 1151.91331 Gairing, Martin; Monien, Burkhard; Tiemann, Karsten 16 2008 Cross-correlation analysis of cryptographically useful boolean functions and s-boxes. Zbl 0993.68032 Sarkar, P.; Maitra, S. 16 2002 Symbolic dynamics: entropy = dimension = complexity. Zbl 1355.37023 Simpson, Stephen G. 16 2015 Analysis of approximation algorithms for \(k\)-set cover using factor-revealing linear programs. Zbl 1170.90461 Athanassopoulos, Stavros; Caragiannis, Ioannis; Kaklamanis, Christos 16 2009 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 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 Stochastic cellular automata solutions to the density classification problem. When randomness helps computing. Zbl 1286.68336 Fatès, Nazim 16 2013 Fixed-parameter enumerability of cluster editing and related problems. Zbl 1209.68360 Damaschke, Peter 16 2010 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 Reachability in two-parametric timed automata with one parameter is EXPSPACE-complete. Zbl 07922397 Göller, Stefan; Hilaire, Mathieu 1 2024 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 2 2023 The space complexity of sum labelling. Zbl 1533.05233 Fernau, Henning; Gajjar, Kshitij 1 2023 The parameterized complexity of \(s\)-club with triangle and seed constraints. Zbl 1525.05034 Garvardt, Jaroslav; Komusiewicz, Christian; Sommer, Frank 1 2023 Subclasses of Ptime interpreted by programming languages. Zbl 07719393 Bhaskar, Siddharth; Kop, Cynthia; Simonsen, Jakob Grue 1 2023 Synchronous Boolean finite dynamical systems on directed graphs over XOR functions. Zbl 07719398 Ogihara, M.; Uchizawa, K. 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 Polynomially ambiguous unary weighted automata over fields. Zbl 07681310 Kostolányi, Peter 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 8 2022 Multistage vertex cover. Zbl 07523542 Fluschnik, Till; Niedermeier, Rolf; Rohm, Valentin; Zschoche, Philipp 6 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 Impartial selection with additive approximation guarantees. Zbl 1493.91029 Caragiannis, Ioannis; Christodoulou, George; Protopapas, Nicos 2 2022 Target set selection parameterized by vertex cover and more. Zbl 1524.90325 Banerjee, Suman; Mathew, Rogers; Panolan, Fahad 2 2022 Stable multi-level monotonic eroders. Zbl 1536.37019 Gács, Péter; Törmä, Ilkka 2 2022 The power of the weighted sum scalarization for approximating multiobjective optimization problems. Zbl 1485.90121 Bazgan, Cristina; Ruzika, Stefan; Thielen, Clemens; Vanderpooten, Daniel 2 2022 Non-existence of stable social groups in information-driven networks. Zbl 1495.91088 Chaintreau, Augustin; Ducoffe, Guillaume; Mazauric, Dorian 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 The complexity of counting \(\mathrm{CSP}^d\). Zbl 1533.68108 Lin, Jiabao 1 2022 Multi-pass streaming algorithms for monotone submodular function maximization. Zbl 1533.68414 Huang, Chien-Chung; Kakimura, Naonori 1 2022 Token sliding on split graphs. Zbl 1517.68273 Belmonte, Rémy; Kim, Eun Jung; Lampis, Michael; Mitsou, Valia; Otachi, Yota; Sikora, Florian 13 2021 Faster parameterized algorithm for cluster vertex deletion. Zbl 1517.68308 Tsur, Dekel 12 2021 Computability of products of chainable continua. Zbl 1535.03228 Čelar, Matea; Iljazović, Zvonko 7 2021 Finite sequentiality of unambiguous max-plus tree automata. Zbl 1517.68211 Paul, Erik 6 2021 Approximation results for makespan minimization with budgeted uncertainty. Zbl 1478.90036 Bougeret, Marin; Jansen, Klaus; Poss, Michael; Rohwedder, Lars 5 2021 The price of fairness for indivisible goods. Zbl 1471.91196 Bei, Xiaohui; Lu, Xinhang; Manurangsi, Pasin; Suksompong, Warut 5 2021 The containment problem for unambiguous register automata and unambiguous timed automata. Zbl 1517.68207 Mottet, Antoine; Quaas, Karin 4 2021 Fast scheduling in distributed transactional memory. Zbl 1464.68036 Busch, Costas; Herlihy, Maurice; Popovic, Miroslav; Sharma, Gokarna 4 2021 On the cycle augmentation problem: hardness and approximation algorithms. Zbl 1473.05292 Gálvez, Waldo; Grandoni, Fabrizio; Jabal Ameli, Afrouz; Sornat, Krzysztof 4 2021 On triangle estimation using tripartite independent set queries. Zbl 1508.68259 Bhattacharya, Anup; Bishnu, Arijit; Ghosh, Arijit; Mishra, Gopinath 4 2021 Parameterized complexity of conflict-free set cover. Zbl 1517.68146 Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh 3 2021 Unpopularity factor in the marriage and roommates problems. Zbl 1518.91175 Ruangwises, Suthee; Itoh, Toshiya 3 2021 Forward looking Huffman coding. Zbl 1517.68111 Klein, Shmuel T.; Saadia, Shoham; Shapira, Dana 3 2021 First-order orbit queries. Zbl 1518.37014 Almagor, Shaull; Ouaknine, Joël; Worrell, James 2 2021 Semi-oblivious chase termination: the sticky case. Zbl 1477.68088 Calautti, Marco; Pieris, Andreas 2 2021 The non-hardness of approximating circuit size. Zbl 1522.68194 Allender, Eric; Ilango, Rahul; Vafa, Neekon 2 2021 Streaming algorithms for bin packing and vector scheduling. Zbl 1528.68408 Cormode, Graham; Veselý, Pavel 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 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 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 Exploration of dynamic cactuses with sub-logarithmic overhead. Zbl 1519.68192 Ilcinkas, David; Wade, Ahmed M. 1 2021 On the relation between structured \(d\)-DNNFs and SDDs. Zbl 1522.68536 Bollig, Beate; Farenholtz, Martin 1 2021 On the complexity of the smallest grammar problem over fixed alphabets. Zbl 1464.68100 Casel, Katrin; Fernau, Henning; Gaspers, Serge; Gras, Benjamin; Schmid, Markus L. 1 2021 On decidability of theories of regular languages. Zbl 1517.68185 Dudakov, Sergey; Karlov, Boris 1 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 The minimum tollbooth problem in atomic network congestion games with unsplittable flows. Zbl 1471.91020 Nickerl, Julian 1 2021 Reachability problems on reliable and lossy queue automata. Zbl 1503.68174 Köcher, Chris 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 Additive number theory via automata theory. Zbl 1475.11040 Rajasekaran, Aayush; Shallit, Jeffrey; Smith, Tim 12 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 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 Conflict free version of covering problems on graphs: classical and parameterized. Zbl 1453.68136 Jain, Pallavi; Kanesh, Lawqueen; Misra, Pranabendu 4 2020 Dependences in strategy logic. Zbl 1484.68100 Gardy, Patrick; Bouyer, Patricia; Markey, Nicolas 3 2020 Lower bound techniques for QBF expansion. Zbl 1471.03081 Beyersdorff, Olaf; Blinkhorn, Joshua 3 2020 Parameterized complexity of min-power asymmetric connectivity. Zbl 1503.68080 Bentert, Matthias; Haag, Roman; Hofer, Christian; Koana, Tomohiro; Nichterlein, André 3 2020 An improved FPT algorithm for independent feedback vertex set. Zbl 1507.68231 Li, Shaohua; Pilipczuk, Marcin 3 2020 On approximating the stationary distribution of time-reversible Markov chains. Zbl 1436.60035 Bressan, Marco; Peserico, Enoch; Pretto, Luca 2 2020 Deterministic min-cost matching with delays. Zbl 1444.68297 Azar, Yossi; Jacob Fanani, Amit 2 2020 Advice complexity of priority algorithms. Zbl 1444.68299 Borodin, Allan; Boyar, Joan; Larsen, Kim S.; Pankratov, Denis 2 2020 On the stab number of rectangle intersection graphs. Zbl 1442.05187 Chakraborty, Dibyayan; Francis, Mathew C. 2 2020 On limitations of structured (deterministic) DNNFs. Zbl 1446.68152 Bollig, Beate; Buttkus, Matthias 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 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 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 Algorithm for online 3-path vertex cover. Zbl 1434.68696 Zhang, Yubai; Zhang, Zhao; Shi, Yishuo; Li, Xianyue 1 2020 Space-efficient algorithms for longest increasing subsequence. Zbl 1433.68632 Kiyomi, Masashi; Ono, Hirotaka; Otachi, Yota; Schweitzer, Pascal; Tarui, Jun 1 2020 Recognizing read-once functions from depth-three formulas. Zbl 1434.68201 Kozachinskiy, Alexander 1 2020 New bounds for truthful scheduling on two unrelated selfish machines. Zbl 1434.68678 Kuryatnikova, Olga; Vera, Juan C. 1 2020 Santha-Vazirani sources, deterministic condensers and very strong extractors. Zbl 1476.68081 Gavinsky, Dmitry; Pudlák, Pavel 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 Effective categoricity of automatic equivalence and nested equivalence structures. Zbl 1485.03109 Carson, Jacob; Cenzer, Douglas; Remmel, Jeffrey B. 1 2020 Verification of quantum computation: an overview of existing approaches. Zbl 1423.68281 Gheorghiu, Alexandru; Kapourniotis, Theodoros; Kashefi, Elham 13 2019 Generic results for concatenation hierarchies. Zbl 1423.68264 Place, Thomas; Zeitoun, Marc 12 2019 A logic for document spanners. Zbl 1430.68081 Freydenberger, Dominik D. 9 2019 On the parameterized complexity of contraction to generalization of trees. Zbl 1435.68119 Agarwal, Akanksha; Saurabh, Saket; Tale, Prafullkumar 8 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 relative succinctness of sentential decision diagrams. Zbl 1435.68320 Bollig, Beate; Buttkus, Matthias 7 2019 The operator approach to entropy games. Zbl 1422.91080 Akian, Marianne; Gaubert, Stéphane; Grand-Clément, Julien; Guillaud, Jérémie 6 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 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 ...and 974 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 7,476 Authors 69 Saurabh, Saket 50 Niedermeier, Rolf 49 Fomin, Fedor V. 46 Paulusma, Daniël 42 Golovach, Petr A. 37 Lohrey, Markus 34 Ganian, Robert 33 Epstein, Leah 32 Lozin, Vadim Vladislavovich 32 Okhotin, Alexander 31 Lokshtanov, Daniel 30 Stephan, Frank 29 Spirakis, Paul G. 28 Bilò, Vittorio 28 Jansen, Bart M. P. 27 Courcelle, Bruno 26 Dabrowski, Konrad Kazimierz 26 Komusiewicz, Christian 26 Mavronicolas, Marios 25 Fellows, Michael Ralph 25 Fernau, Henning 25 Pilipczuk, Michał 25 Rigo, Michel 24 Caragiannis, Ioannis 24 Raman, Venkatesh 23 Bodlaender, Hans L. 23 Gutin, Gregory Z. 23 Heggernes, Pinar 23 Otachi, Yota 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 21 Vogler, Heiko 20 Bazgan, Cristina 20 Gurski, Frank 20 Kwon, O. joung 20 Maletti, Andreas 20 Mitrana, Victor 20 Monnot, Jérôme 20 Pelc, Andrzej 20 Szeider, Stefan 20 Xiao, Mingyu 19 Cai, Jin-Yi 19 Jain, Sanjay 19 Manea, Florin 19 Souza, Uéverton S. 18 Doerr, Benjamin 18 Droste, Manfred 18 Flocchini, Paola 18 Kowalski, Dariusz R. 18 Levin, Asaf 18 Rossmanith, Peter 18 Santoro, Nicola 17 Böckenhauer, Hans-Joachim 17 Busch, Costas 17 Chen, Jian-er 17 Nichterlein, André 17 Papadopoulos, Charis 17 Zamaraev, Victor A. 16 Bača, Martin 16 Ban, Jungchao 16 Bodirsky, Manuel 16 Chang, Chih-Hung 16 Downey, Rodney Graham 16 Fülöp, Zoltán 16 Marx, Dániel 16 Molter, Hendrik 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 Hemaspaandra, Edith 15 Kanté, Mamadou Moustapha 15 Lutz, Jack H. 15 Makowsky, Johann-Andreas 15 Pilipczuk, Marcin L. 15 Place, Thomas 15 Rautenbach, Dieter 15 Rzążewski, Paweł 15 Suchý, Ondřej 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 ...and 7,376 more Authors all top 5 Cited in 417 Journals 797 Theoretical Computer Science 319 Algorithmica 285 Theory of Computing Systems 224 Discrete Applied Mathematics 197 Journal of Computer and System Sciences 181 Information and Computation 150 Information Processing Letters 96 Journal of Combinatorial Optimization 90 International Journal of Foundations of Computer Science 80 SIAM Journal on Computing 80 Distributed Computing 66 SIAM Journal on Discrete Mathematics 61 Logical Methods in Computer Science 51 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 27 Computational Geometry 26 Acta Informatica 26 Computational Complexity 25 ACM Transactions on Computational Logic 24 The Journal of Symbolic Logic 24 Mathematics of Operations Research 24 International Journal of Algebra and Computation 24 Mathematical Programming. Series A. Series B 23 Natural Computing 22 Operations Research Letters 22 Games and Economic Behavior 21 Discrete Optimization 20 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 Graph Algorithms and Applications 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 Annals of Mathematics and Artificial Intelligence 15 Discrete Mathematics and Theoretical Computer Science. DMTCS 15 RAIRO. Theoretical Informatics and Applications 14 Applied Mathematics and Computation 14 Algorithms 13 Journal of Algebra 13 Annals of Operations Research 13 The Electronic Journal of Combinatorics 13 ACM Journal of Experimental Algorithmics 13 Discrete Mathematics, Algorithms and Applications 12 Operations Research 12 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 Quantum Information Processing 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 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 Journal of Automata, Languages and Combinatorics 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 Topology and its Applications 7 International Journal of Approximate Reasoning 7 Formal Methods in System Design 7 Fundamenta Informaticae 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 ...and 317 more Journals all top 5 Cited in 53 Fields 4,656 Computer science (68-XX) 1,577 Combinatorics (05-XX) 823 Operations research, mathematical programming (90-XX) 680 Mathematical logic and foundations (03-XX) 638 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 225 Information and communication theory, circuits (94-XX) 155 Group theory and generalizations (20-XX) 115 Number theory (11-XX) 115 Dynamical systems and ergodic theory (37-XX) 99 Probability theory and stochastic processes (60-XX) 91 Biology and other natural sciences (92-XX) 89 Quantum theory (81-XX) 60 Order, lattices, ordered algebraic structures (06-XX) 57 Numerical analysis (65-XX) 52 Measure and integration (28-XX) 45 Statistics (62-XX) 43 Convex and discrete geometry (52-XX) 42 General algebraic systems (08-XX) 39 Systems theory; control (93-XX) 37 Linear and multilinear algebra; matrix theory (15-XX) 37 General topology (54-XX) 26 Statistical mechanics, structure of matter (82-XX) 18 Category theory; homological algebra (18-XX) 16 Associative rings and algebras (16-XX) 13 Algebraic geometry (14-XX) 12 History and biography (01-XX) 10 Functions of a complex variable (30-XX) 10 Calculus of variations and optimal control; optimization (49-XX) 9 General and overarching topics; collections (00-XX) 9 Operator theory (47-XX) 8 Ordinary differential equations (34-XX) 8 Manifolds and cell complexes (57-XX) 7 Commutative algebra (13-XX) 7 Topological groups, Lie groups (22-XX) 7 Real functions (26-XX) 5 Geometry (51-XX) 4 Approximations and expansions (41-XX) 4 Algebraic topology (55-XX) 4 Mechanics of deformable solids (74-XX) 3 Functional analysis (46-XX) 3 Differential geometry (53-XX) 3 Mechanics of particles and systems (70-XX) 2 Partial differential equations (35-XX) 2 Abstract harmonic analysis (43-XX) 2 Fluid mechanics (76-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 Optics, electromagnetic theory (78-XX) 1 Relativity and gravitational theory (83-XX) Citations by Year