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