Journal of Computer and System Sciences Short Title: J. Comput. Syst. Sci. Publisher: Elsevier (Academic Press), San Diego, CA ISSN: 0022-0000 Online: http://www.sciencedirect.com/science/journal/00220000 Comments: Indexed cover-to-cover Documents Indexed: 3,072 Publications (since 1967) References Indexed: 2,799 Publications with 69,723 References. all top 5 Latest Issues 134 (2023) 133 (2023) 132 (2023) 131 (2023) 130 (2022) 129 (2022) 128 (2022) 127 (2022) 126 (2022) 125 (2022) 124 (2022) 123 (2022) 122 (2021) 121 (2021) 120 (2021) 119 (2021) 118 (2021) 117 (2021) 116 (2021) 115 (2021) 114 (2020) 113 (2020) 112 (2020) 111 (2020) 110 (2020) 109 (2020) 108 (2020) 107 (2020) 106 (2019) 105 (2019) 104 (2019) 103 (2019) 102 (2019) 101 (2019) 100 (2019) 99 (2019) 98 (2018) 97 (2018) 96 (2018) 95 (2018) 94 (2018) 93 (2018) 92 (2018) 91 (2018) 90 (2017) 89 (2017) 88 (2017) 87 (2017) 86 (2017) 85 (2017) 84 (2017) 83 (2017) 82, No. 8 (2016) 82, No. 7 (2016) 82, No. 6 (2016) 82, No. 5 (2016) 82, No. 4 (2016) 82, No. 3 (2016) 82, No. 2 (2016) 82, No. 1, Part A (2016) 81, No. 8 (2015) 81, No. 7 (2015) 81, No. 6 (2015) 81, No. 5 (2015) 81, No. 4 (2015) 81, No. 3 (2015) 81, No. 2 (2015) 81, No. 1 (2015) 80, No. 8 (2014) 80, No. 7 (2014) 80, No. 6 (2014) 80, No. 5 (2014) 80, No. 4 (2014) 80, No. 3 (2014) 80, No. 2 (2014) 80, No. 1 (2014) 79, No. 8 (2013) 79, No. 7 (2013) 79, No. 6 (2013) 79, No. 5 (2013) 79, No. 4 (2013) 79, No. 3 (2013) 79, No. 1 (2013) 78, No. 6 (2012) 78, No. 5 (2012) 78, No. 4 (2012) 78, No. 3 (2012) 78, No. 2 (2012) 78, No. 1 (2012) 77, No. 6 (2011) 77, No. 5 (2011) 77, No. 4 (2011) 77, No. 3 (2011) 77, No. 2 (2011) 77, No. 1 (2011) 76, No. 8 (2010) 76, No. 7 (2010) 76, No. 6 (2010) 76, No. 5 (2010) 76, No. 3-4 (2010) ...and 186 more Volumes all top 5 Authors 25 Papadimitriou, Christos Harilaos 24 Engelfriet, Joost 22 Jain, Sanjay 18 Ullman, Jeffrey David 17 Fomin, Fedor V. 17 Yannakakis, Mihalis 16 Niedermeier, Rolf 16 Rozenberg, Grzegorz 16 Saurabh, Saket 15 Ibarra, Oscar H. 15 Stephan, Frank 14 Fellows, Michael Ralph 14 Ginsburg, Seymour 13 Greibach, Sheila A. 13 Gutin, Gregory Z. 13 Vianu, Victor 12 Abiteboul, Serge 12 Allender, Eric W. 12 Galil, Zvi 12 Goldberg, Leslie Ann 12 Hemaspaandra, Lane A. 12 Vardi, Moshe Ya’akov 11 Cai, Jin-Yi 11 Case, John 11 Li, Ming 11 Reif, John H. 11 Salomaa, Arto Kustaa 11 Van Gucht, Dirk 10 Alon, Noga 10 Bshouty, Nader H. 10 Chen, Jian-er 10 Downey, Rodney Graham 10 Fortnow, Lance J. 10 Pippenger, Nicholas J. 10 Spirakis, Paul G. 9 Bloom, Stephen L. 9 Epstein, Leah 9 Goldman, Sally A. 9 Hsieh, Sun-Yuan 9 Impagliazzo, Russell 9 Kolaitis, Phokion G. 9 Lipton, Richard Jay 9 Lynch, Nancy Ann 9 McKenzie, Pierre 9 Milo, Tova 9 Paulusma, Daniël 9 Sagiv, Yehoshua 9 Szeider, Stefan 9 Van den Bussche, Jan 8 Buhrman, Harry 8 Fagin, Ronald 8 Gąsieniec, Leszek Antoni 8 Golovach, Petr A. 8 Gyssens, Marc 8 Harel, David 8 Hartmanis, Juris 8 Kanj, Iyad A. 8 Karpinski, Marek 8 Kowalski, Dariusz R. 8 Libkin, Leonid O. 8 Long, Philip M. 8 Maass, Wolfgang 8 Saks, Michael E. 8 Servedio, Rocco A. 8 Suciu, Dan Mircea 8 Thilikos, Dimitrios M. 8 Tompa, Martin 8 Xiang, Yang 8 Yeo, Anders 7 Aho, Alfred Vaino 7 Barolli, Leonard 7 Blum, Edward Kenneth 7 Book, Ronald Vernon 7 Cohen, Rina S. 7 Cook, Stephen Arthur 7 Feige, Uriel 7 Fernau, Henning 7 Fischer, Patrick Carl 7 Goldstine, Jonathan 7 Gottlob, Georg 7 Guo, Jiong 7 Honda, Namio 7 Hopcroft, John Edward H. 7 Immerman, Neil 7 Jerrum, Mark R. 7 Jiang, Tao 7 Kleinberg, Jon Michael 7 Köbler, Johannes 7 Ladner, Richard E. 7 Ma, Bin 7 Paredaens, Jan 7 Pnueli, Amir 7 Rabani, Yuval 7 Raghavan, Prabhakar 7 Rothe, Jörg-Matthias 7 Selman, Alan Louis 7 Spanier, Edwin Henry 7 Srinivasan, Aravind 7 Takizawa, Makoto 7 Taniar, David ...and 3,998 more Authors all top 5 Fields 2,794 Computer science (68-XX) 310 Mathematical logic and foundations (03-XX) 255 Combinatorics (05-XX) 149 Information and communication theory, circuits (94-XX) 144 Operations research, mathematical programming (90-XX) 87 General and overarching topics; collections (00-XX) 78 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 61 Biology and other natural sciences (92-XX) 58 Numerical analysis (65-XX) 41 Group theory and generalizations (20-XX) 31 Number theory (11-XX) 29 Category theory; homological algebra (18-XX) 27 Probability theory and stochastic processes (60-XX) 27 Statistics (62-XX) 24 Quantum theory (81-XX) 24 Systems theory; control (93-XX) 23 Linear and multilinear algebra; matrix theory (15-XX) 20 Order, lattices, ordered algebraic structures (06-XX) 19 Dynamical systems and ergodic theory (37-XX) 15 General algebraic systems (08-XX) 13 Convex and discrete geometry (52-XX) 8 Calculus of variations and optimal control; optimization (49-XX) 5 Associative rings and algebras (16-XX) 5 Approximations and expansions (41-XX) 5 General topology (54-XX) 4 History and biography (01-XX) 4 Field theory and polynomials (12-XX) 4 Ordinary differential equations (34-XX) 4 Operator theory (47-XX) 4 Geometry (51-XX) 4 Statistical mechanics, structure of matter (82-XX) 3 Algebraic geometry (14-XX) 3 Algebraic topology (55-XX) 2 Topological groups, Lie groups (22-XX) 2 Partial differential equations (35-XX) 2 Harmonic analysis on Euclidean spaces (42-XX) 2 Manifolds and cell complexes (57-XX) 1 Commutative algebra (13-XX) 1 Real functions (26-XX) 1 Measure and integration (28-XX) 1 Difference and functional equations (39-XX) 1 Integral equations (45-XX) 1 Functional analysis (46-XX) 1 Global analysis, analysis on manifolds (58-XX) 1 Mechanics of particles and systems (70-XX) 1 Optics, electromagnetic theory (78-XX) Publications by Year all cited Publications top 5 cited Publications Citations contained in zbMATH Open 2,423 Publications have been cited 36,828 times in 24,636 Documents Cited by ▼ Year ▼ Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Zbl 0367.68034Booth, Kellogg S.; Lueker, George S. 453 1976 A decision-theoretic generalization of on-line learning and an application to boosting. Zbl 0880.68103Freund, Yoav; Schapire, Robert E. 445 1997 Optimization, approximation, and complexity classes. Zbl 0765.68036Papadimitriou, Christos H.; Yannakakis, Mihalis 425 1991 Which problems have strongly exponential complexity? Zbl 1006.68052Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis 417 2001 Approximation algorithms for combinatorial problems. Zbl 0296.65036Johnson, David S. 371 1974 Relationships between nondeterministic and deterministic tape complexities. Zbl 0188.33502Savitch, W. J. 364 1970 Computing with membranes. Zbl 0956.68055Păun, Gheorghe 329 2000 Probabilistic encryption. Zbl 0563.94013Goldwasser, Shafi; Micali, Silvio 304 1984 On the complexity of \(k\)-SAT. Zbl 0990.68079Impagliazzo, Russell; Paturi, Ramamohan 304 2001 Propositional dynamic logic of regular programs. Zbl 0408.03014Fischer, Michael J.; Ladner, Richard E. 246 1979 On the computational power of pushdown automata. Zbl 0207.01701Aho, A. V.; Ullman, J. D.; Hopcroft, J. E. 245 1970 Universal classes of hash functions. Zbl 0412.68090Carter, J. Lawrence; Wegman, Mark N. 231 1979 Variable precision rough set model. Zbl 0764.68162Ziarko, Wojciech 230 1993 Time bounds for selection. Zbl 0278.68033Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. 228 1973 A theory of type polymorphism in programming. Zbl 0388.68003Milner, Robin 201 1978 On problems without polynomial kernels. Zbl 1192.68288Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny 201 2009 A data structure for dynamic trees. Zbl 0509.68058Sleator, Daniel D.; Tarjan, Robert Endre 199 1983 The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029Lewis, John M.; Yannakakis, Mihalis 191 1980 Parallel program schemata. Zbl 0198.32603Karp, Richard M.; Miller, Raymond E. 185 1969 Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061Khot, Subhash; Regev, Oded 183 2008 Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). Zbl 0667.68059Barrington, David A. 175 1989 Hardness vs randomness. Zbl 0821.68057Nisan, Noam; Wigderson, Avi 165 1994 Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074Yannakakis, Mihalis 164 1991 Self-testing/correcting with applications to numerical problems. Zbl 0795.68131Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt 160 1993 Optimization of LR(k) parsers. Zbl 0264.68032Aho, A. V.; Ullman, J. D. 159 1972 On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048Papadimitriou, Christos H. 153 1994 How easy is local search? Zbl 0655.68074Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 145 1988 Fast probabilistic algorithms for Hamiltonian circuits and matchings. Zbl 0437.05040Angluin, D.; Valiant, L. G. 143 1979 A linear-time algorithm for a special case of disjoint set union. Zbl 0572.68058Gabow, Harold N.; Tarjan, Robert Endre 139 1985 Handle-rewriting hypergraph grammars. Zbl 0825.68446Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz 138 1993 On uniform circuit complexity. Zbl 0462.68013Ruzzo, Walter L. 138 1981 Isomorphism of graphs of bounded valence can be tested in polynomial time. Zbl 0493.68064Luks, Eugene M. 135 1982 Finding patterns common to a set of strings. Zbl 0454.68108Angluin, Dana 132 1980 New hash functions and their use in authentication and set equality. Zbl 0461.68074Wegman, Mark N.; Carter, J. Lawrence 131 1981 Tree acceptors and some of their applications. Zbl 0212.02901Doner, John 126 1970 The space complexity of approximating the frequency moments. Zbl 0938.68153Alon, Noga; Matias, Yossi; Szegedy, Mario 123 1999 The complexity of optimization problems. Zbl 0652.68040Krentel, Mark W. 117 1988 A faster algorithm computing string edit distances. Zbl 0436.68044Masek, William J.; Paterson, Michael S. 115 1980 Fast algorithms for bin packing. Zbl 0284.68023Johnson, David S. 114 1974 On uniformity within \(NC^ 1\). Zbl 0719.68023Barrington, David A. Mix; Immerman, Neil; Straubing, Howard 114 1990 Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040Achlioptas, Dimitris 114 2003 NP-complete scheduling problems. Zbl 0313.68054Ullman, J. D. 113 1975 Maintenance of configurations in the plane. Zbl 0474.68082Overmars, Mark H.; van Leeuwen, Jan 112 1981 Space-bounded reducibility among combinatorial problems. Zbl 0317.02039Jones, Neil D. 111 1975 What’s decidable about hybrid automata? Zbl 0920.68091Henzinger, Thomas A.; Kopke, Peter W.; Puri, Anuj; Varaiya, Pravin 111 1998 Structure and complexity of relational queries. Zbl 0511.68073Chandra, Ashok; Harel, David 109 1982 Riemann’s hypothesis and tests for primality. Zbl 0349.68025Miller, Gary L. 108 1976 The complexity of facets (and some facets of complexity). Zbl 0571.68028Papadimitriou, C. H.; Yannakakis, M. 108 1984 Relaxing the uniformity and independence assumptions using the concept of fractal dimension. Zbl 0889.68050Faloutsos, Christos; Kamel, Ibrahim 106 1997 Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029Babai, László; Moran, Shlomo 106 1988 Reversal-bounded multipushdown machines. Zbl 0309.68043Baker, Brenda S.; Book, Ronald V. 102 1974 Classifying regular events in symbolic logic. Zbl 0503.68055Thomas, Wolfgang 100 1982 A framework for solving VLSI graph layout problems. Zbl 0543.68052Bhatt, Sandeep N.; Leighton, Frank Thompson 100 1984 Groups, the theory of ends, and context-free languages. Zbl 0537.20011Muller, David E.; Schupp, Paul E. 98 1983 On the complexity of some two-person perfect-information games. Zbl 0383.90112Schaefer, Thomas J. 94 1978 Marked directed graphs. Zbl 0238.05109Commoner, F.; Holt, A. W.; Even, S.; Pnueli, A. 94 1971 Randomness is linear in space. Zbl 0846.68041Nisan, Noam; Zuckerman, David 93 1996 Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144Fortnow, Lance; Santhanam, Rahul 92 2011 On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Zbl 0752.68009Bar-Yehuda, Reuven; Goldreich, Oded; Itai, Alon 92 1992 Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Zbl 0263.94019Amoroso, S.; Patt, Y. N. 92 1972 A complete inference system for a class of regular behaviours. Zbl 0562.68065Milner, Robin 90 1984 A tight bound on approximating arbitrary metrics by tree metrics. Zbl 1071.68082Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal 90 2004 Making data structures persistent. Zbl 0667.68026Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E. 90 1989 Process complexity and effective random tests. Zbl 0273.68036Schnorr, C. P. 89 1973 Multiattribute decision making models and methods using intuitionistic fuzzy sets. Zbl 1066.90052Li, Deng-Feng 89 2005 Probabilistic construction of deterministic algorithms: approximating packing integer programs. Zbl 0659.90066Raghavan, Prabhakar 89 1988 Decision procedures and expressiveness in the temporal logic of branching time. Zbl 0559.68051Emerson, E. Allen; Halpern, Joseph Y. 87 1985 Topologically sweeping an arrangement. Zbl 0676.68013Edelsbrunner, Herbert; Guibas, Leonidas J. 87 1989 Generalized sequential machine maps. Zbl 0198.03303Thatcher, J. W. 87 1970 An information statistics approach to data stream and communication complexity. Zbl 1074.68022Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D. 86 2004 Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Zbl 0493.68043Mahaney, Stephen R. 86 1982 In search of an easy witness: Exponential time vs. probabilistic polynomial time. Zbl 1059.68047Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi 85 2002 On the complexity of teaching. Zbl 0939.68770Goldman, Sally A.; Kearns, Michael J. 84 1995 Minimum disclosure proofs of knowledge. Zbl 0656.68109Brassard, Gilles; Chaum, David; Crépeau, Claude 84 1988 Natural proofs. Zbl 0884.68055Razborov, Alexander A.; Rudich, Steven 83 1997 Almost everywhere high nonuniform complexity. Zbl 0767.68043Lutz, Jack H. 83 1992 Surpassing the information theoretic bound with fusion trees. Zbl 0795.68049Fredman, Michael L.; Willard, Dan E. 81 1993 Computable queries for relational data bases. Zbl 0456.68128Chandra, Ashok K.; Harel, David 81 1980 Zero knowledge and the chromatic number. Zbl 0921.68089Feige, Uriel; Kilian, Joe 79 1998 Tesselations with local transformations. Zbl 0246.94037Richardson, D. 79 1972 Linear unification. Zbl 0371.68013Paterson, M. S.; Wegman, M. N. 78 1978 Automata-theoretic techniques for modal logics of programs. Zbl 0622.03017Vardi, Moshe Y.; Wolper, Pierre 78 1986 Adherences of languages. Zbl 0471.68052Boasson, Luc; Nivat, Maurice 77 1980 Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045Gabber, Ofer; Galil, Zvi 77 1981 Varieties of ordered algebras. Zbl 0337.06008Bloom, Stephen L. 76 1976 Conjunctive-query containment and constraint satisfaction. Zbl 0963.68059Kolaitis, Phokion G.; Vardi, Moshe Y. 76 2000 Embedding planar graphs in four pages. Zbl 0673.05022Yannakakis, Mihalis 76 1989 The average height of binary trees and other simple trees. Zbl 0499.68027Flajolet, Philippe; Odlyzko, Andrew 75 1982 Classical complexity and quantum entanglement. Zbl 1093.81012Gurvits, Leonid 75 2004 Tree-size bounded alternation. Zbl 0445.68034Ruzzo, Walter L. 72 1980 Power domains. Zbl 0391.68011Smyth, M. B. 71 1978 Solving reflexive domain equations in a category of complete metric spaces. Zbl 0717.18002America, Pierre; Rutten, Jan 70 1989 Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Zbl 0155.01802Thatcher, J. W. 70 1967 Probabilistic counting algorithms for data base applications. Zbl 0583.68059Flajolet, Philippe; Martin, G. Nigel 69 1985 Clustering with qualitative information. Zbl 1094.68075Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony 69 2005 Semantics of probabilistic programs. Zbl 0476.68019Kozen, Dexter 68 1981 Reversibility and surjectivity problems of cellular automata. Zbl 0802.68090Kari, Jarkko 67 1994 Teaching a smarter learner. Zbl 1152.68451Goldman, Sally A.; Mathias, H. David 67 1996 On the computational power of neural nets. Zbl 0826.68104Siegelmann, Hava T.; Sontag, Eduardo D. 67 1995 Faster shortest-path algorithms for planar graphs. Zbl 0880.68099Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam 67 1997 Parameterized complexity of multi-node hubs. Zbl 07601249Saurabh, Saket; Zehavi, Meirav 1 2023 Incompressibility of \(H\)-free edge modification problems: towards a dichotomy. Zbl 07466698Marx, Dániel; Sandeep, R. B. 3 2022 Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Zbl 1479.68002Golovach, Petr A.; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang 2 2022 Many-visits TSP revisited. Zbl 1478.68464Kowalik, Łukasz; Li, Shaohua; Nadara, Wojciech; Smulewicz, Marcin; Wahlström, Magnus 2 2022 An improved algorithm for the Steiner tree problem with bounded edge-length. Zbl 1472.68111Chen, Chi-Yeh; Hsieh, Sun-Yuan 1 2022 A \(4+\epsilon\) approximation for \(k\)-connected subgraphs. Zbl 1472.68215Nutov, Zeev 1 2022 Word equations in non-deterministic linear space. Zbl 1472.68068Jeż, Artur 1 2022 Normalized information distance and the oscillation hierarchy. Zbl 1481.68031Ambos-Spies, Klaus; Merkle, Wolfgang; Terwijn, Sebastiaan A. 1 2022 Approximate CVP\(_p\) in time \(2^{0.802n}\). Zbl 1478.68449Eisenbrand, Friedrich; Venzin, Moritz 1 2022 Greedy routing and the algorithmic small-world phenomenon. Zbl 07466699Bringmann, Karl; Keusch, Ralph; Lengler, Johannes; Maus, Yannic; Molla, Anisur R. 1 2022 Length-bounded cuts: proper interval graphs and structural parameters. Zbl 07499478Bentert, Matthias; Heeger, Klaus; Knop, Dušan 1 2022 Medians in median graphs and their cube complexes in linear time. Zbl 1483.68250Bénéteau, Laurine; Chalopin, Jérémie; Chepoi, Victor; Vaxès, Yann 1 2022 Multistage knapsack. Zbl 1489.90147Bampis, Evripidis; Escoffier, Bruno; Teiller, Alexandre 1 2022 Complexity of fixed point counting problems in Boolean networks. Zbl 1483.68240Bridoux, Florian; Durbec, Amélia; Perrot, Kevin; Richard, Adrien 1 2022 Unlabeled sample compression schemes and corner peelings for ample and maximum classes. Zbl 1483.68281Chalopin, Jérémie; Chepoi, Victor; Moran, Shay; Warmuth, Manfred K. 1 2022 Polynomially ambiguous probabilistic automata on restricted languages. Zbl 1483.68156Bell, Paul C. 1 2022 The complexity of reachability in parametric Markov decision processes. Zbl 1477.68124Junges, Sebastian; Katoen, Joost-Pieter; Pérez, Guillermo A.; Winkler, Tobias 7 2021 Assigning times to minimise reachability in temporal graphs. Zbl 1464.68283Enright, Jessica; Meeks, Kitty; Skerman, Fiona 5 2021 Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1477.68115Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 5 2021 On temporal graph exploration. Zbl 1477.68222Erlebach, Thomas; Hoffmann, Michael; Kammer, Frank 5 2021 Deleting edges to restrict the size of an epidemic in temporal networks. Zbl 1477.68221Enright, Jessica; Meeks, Kitty; Mertzios, George B.; Zamaraev, Viktor 5 2021 Preimage problems for deterministic finite automata. Zbl 1464.68148Berlinkov, Mikhail V.; Ferens, Robert; Szykuła, Marek 4 2021 Exploration of dynamic networks: tight bounds on the number of agents. Zbl 07396415Gotoh, Tsuyoshi; Flocchini, Paola; Masuzawa, Toshimitsu; Santoro, Nicola 3 2021 Sliding window temporal graph coloring. Zbl 1473.68123Mertzios, George B.; Molter, Hendrik; Zamaraev, Viktor 3 2021 Measuring what matters: a hybrid approach to dynamic programming with treewidth. Zbl 07368162Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Kwon, O-joung 3 2021 The Hairy Ball problem is PPAD-complete. Zbl 07396417Goldberg, Paul W.; Hollender, Alexandros 2 2021 Block trees. Zbl 1477.68076Belazzougui, Djamal; Cáceres, Manuel; Gagie, Travis; Gawrychowski, Paweł; Kärkkäinen, Juha; Navarro, Gonzalo; Ordóñez, Alberto; Puglisi, Simon J.; Tabei, Yasuo 2 2021 A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem. Zbl 1480.68013Li, Xingfu; Zhu, Daming; Wang, Lusheng 2 2021 Temporal cliques admit sparse spanners. Zbl 07368158Casteigts, Arnaud; Peters, Joseph G.; Schoeters, Jason 2 2021 Lattice-based weak-key analysis on single-server outsourcing protocols of modular exponentiations and basic countermeasures. Zbl 07368159Zheng, Yunhai; Tian, Chengliang; Zhang, Hanlin; Yu, Jia; Li, Fengjun 2 2021 Edge fault-tolerance analysis of maximally edge-connected graphs and super edge-connected graphs. Zbl 1464.68035Zhao, Shuang; Chen, Zongqing; Yang, Weihua; Meng, Jixiang 1 2021 Deterministic protocols in the SINR model without knowledge of coordinates. Zbl 1467.68207Moses, William K. jun.; Vaya, Shailesh 1 2021 Understanding PPA-completeness. Zbl 1464.68121Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying 1 2021 On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Zbl 1480.91023Caragiannis, Ioannis; Fanelli, Angelo 1 2021 Parameterized \(k\)-clustering: tractability island. Zbl 1477.68132Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill 1 2021 Reachability relations of timed pushdown automata. Zbl 1484.68079Clemente, Lorenzo; Lasota, Sławomir 1 2021 Grammar-compressed indexes with logarithmic search time. Zbl 1477.68104Claude, Francisco; Navarro, Gonzalo; Pacheco, Alejandro 1 2021 The temporal explorer who returns to the base. Zbl 07365388Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Raptopoulos, Christoforos 1 2021 When are emptiness and containment decidable for probabilistic automata? Zbl 1477.68150Daviaud, Laure; Jurdziński, Marcin; Lazić, Ranko; Mazowiecki, Filip; Pérez, Guillermo A.; Worrell, James 1 2021 Bisection of bounded treewidth graphs by convolutions. Zbl 1477.68220Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. 1 2021 Bidding mechanisms in graph games. Zbl 1480.91053Avni, Guy; Henzinger, Thomas A.; Žikelić, Đorđe 1 2021 A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion. Zbl 1482.68110Donkers, Huib; Jansen, Bart M. P. 1 2021 The complexity of finding small separators in temporal graphs. Zbl 1436.68265Zschoche, Philipp; Fluschnik, Till; Molter, Hendrik; Niedermeier, Rolf 19 2020 Temporal vertex cover with a sliding time window. Zbl 1436.68219Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Zamaraev, Viktor 10 2020 Unique end of potential line. Zbl 1461.68086Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul 9 2020 2-D Tucker is PPA complete. Zbl 1436.68127Aisenberg, James; Bonet, Maria Luisa; Buss, Sam 8 2020 Counting and enumerating tree-child networks and their subclasses. Zbl 1448.92147Cardona, Gabriel; Zhang, Louxin 7 2020 Subexponential algorithms for variants of the homomorphism problem in string graphs. Zbl 1435.68243Okrasa, Karolina; Rzążewski, Paweł 7 2020 Graphs are not universal for online computability. Zbl 1476.03046Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel 6 2020 LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs. Zbl 1436.68236Frati, Fabrizio; Patrignani, Maurizio; Roselli, Vincenzo 4 2020 How fast can we reach a target vertex in stochastic temporal graphs? Zbl 1456.68124Akrida, Eleni C.; Mertzios, George B.; Nikoletseas, Sotiris; Raptopoulos, Christoforos; Spirakis, Paul G.; Zamaraev, Viktor 4 2020 Online bin packing with cardinality constraints resolved. Zbl 1442.68269Balogh, János; Békési, József; Dósa, György; Epstein, Leah; Levin, Asaf 4 2020 On Weisfeiler-Leman invariance: subgraph counts and related graph properties. Zbl 1450.05056Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg 4 2020 Vulnerability of super extra edge-connected graphs. Zbl 1436.68225Cheng, Chia-Wen; Hsieh, Sun-Yuan; Klasing, Ralf 3 2020 Clique-width and well-quasi-ordering of triangle-free graph classes. Zbl 1442.05184Dabrowski, Konrad K.; Lozin, Vadim V.; Paulusma, Daniël 3 2020 Deciding probabilistic bisimilarity distance one for probabilistic automata. Zbl 1432.68247Tang, Qiyi; van Breugel, Franck 3 2020 Eccentricity terrain of \(\delta\)-hyperbolic graphs. Zbl 1450.05017Dragan, Feodor F.; Guarnera, Heather M. 3 2020 Hitting minors on bounded treewidth graphs. III. Lower bounds. Zbl 1435.68121Baste, Julien; Sau, Ignasi; Thilikos, Dimitrios M. 3 2020 On decidability and complexity of low-dimensional robot games. Zbl 1436.91002Niskanen, R.; Potapov, I.; Reichert, J. 2 2020 Subquadratic non-adaptive threshold group testing. Zbl 1432.68177De Marco, Gianluca; Jurdziński, Tomasz; Kowalski, Dariusz R.; Różański, Michał; Stachowiak, Grzegorz 2 2020 Complexity of control in judgment aggregation for uniform premise-based quota rules. Zbl 1448.91100Baumeister, Dorothea; Erdélyi, Gábor; Erdélyi, Olivia J.; Rothe, Jörg; Selker, Ann-Kathrin 2 2020 The complexity of synthesizing elementary net systems relative to natural parameters. Zbl 1435.68214Rosenke, Christian; Tredup, Ronny 2 2020 The complexity of planar Boolean #CSP with complex weights. Zbl 1436.68135Guo, Heng; Williams, Tyson 1 2020 Contextuality in multipartite pseudo-telepathy graph games. Zbl 1442.81013Anshu, Anurag; Høyer, Peter; Mhalla, Mehdi; Perdrix, Simon 1 2020 On the degrees of non-regularity and non-context-freeness. Zbl 1447.68006Bordihn, Henning; Mitrana, Victor 1 2020 An improved algorithm for the minmax regret path center problem on trees. Zbl 1446.68126Wang, Biing-Feng; Ye, Jhih-Hong; Li, Chih-Yu 1 2020 Universal stability in multi-hop radio networks. Zbl 1473.68031Chlebus, Bogdan S.; Cholvi, Vicent; Kowalski, Dariusz R. 1 2020 Space efficient representations of finite groups. Zbl 1461.68061Das, Bireswar; Sharma, Shivdutt; Vaidyanathan, P. R. 1 2020 The computational power of parsing expression grammars. Zbl 1432.68211Loff, Bruno; Moreira, Nelma; Reis, Rogério 1 2020 A multivariate analysis of the strict terminal connection problem. Zbl 1435.90040Melo, Alexsander A.; Figueiredo, Celina M. H.; Souza, Uéverton S. 1 2020 Disconnected cuts in claw-free graphs. Zbl 1450.05073Martin, Barnaby; Paulusma, Daniël; van Leeuwen, Erik Jan 1 2020 A counterexample to Thiagarajan’s conjecture on regular event structures. Zbl 1442.68131Chalopin, Jérémie; Chepoi, Victor 1 2020 Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule? Zbl 1445.68171Misra, Neeldhara; Panolan, Fahad; Saurabh, Saket 1 2020 When are epsilon-nets small? Zbl 1435.68219Kupavskii, Andrey; Zhivotovskiy, Nikita 1 2020 Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence. Zbl 1435.68169Jančar, Petr 1 2020 Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. Zbl 1435.68221Backens, Miriam; Bulatov, Andrei; Goldberg, Leslie Ann; McQuillan, Colin; Živný, Stanislav 1 2020 On the transformation capability of feasible mechanisms for programmable matter. Zbl 1421.68158Michail, Othon; Skretas, George; Spirakis, Paul G. 10 2019 Temporal flows in temporal networks. Zbl 1423.68324Akrida, Eleni C.; Czyzowicz, Jurek; Gąsieniec, Leszek; Kuszner, Łukasz; Spirakis, Paul G. 7 2019 Packet latency of deterministic broadcasting in adversarial multiple access channels. Zbl 1408.94922Anantharamu, Lakshmi; Chlebus, Bogdan S.; Kowalski, Dariusz R.; Rokicki, Mariusz A. 6 2019 Structural sparsity of complex networks: bounded expansion in random models and real-world graphs. Zbl 1425.05149Demaine, Erik D.; Reidl, Felix; Rossmanith, Peter; F. S. Sánchez Villaamil, Fernando; Sikdar, Somnath; Sullivan, Blair D. 6 2019 Copyless cost-register automata: structure, expressiveness, and closure properties. Zbl 1421.68050Mazowiecki, Filip; Riveros, Cristian 4 2019 The optimal absolute ratio for online bin packing. Zbl 1421.68238Balogh, János; Békési, József; Dósa, György; Sgall, Jiří; van Stee, Rob 4 2019 Parameterized aspects of triangle enumeration. Zbl 1430.68176Bentert, Matthias; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf 4 2019 A game characterisation of tree-like Q-resolution size. Zbl 1425.03028Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek 3 2019 Bounding clique-width via perfect graphs. Zbl 1428.05220Dabrowski, Konrad K.; Huang, Shenwei; Paulusma, Daniël 3 2019 Complexity of road coloring with prescribed reset words. Zbl 1425.68236Vorel, Vojtěch; Roman, Adam 3 2019 On notions of distortion and an almost minimum spanning tree with constant average distortion. Zbl 1423.68326Bartal, Yair; Filtser, Arnold; Neiman, Ofer 3 2019 HV-planarity: algorithms and complexity. Zbl 1409.68211Didimo, Walter; Liotta, Giuseppe; Patrignani, Maurizio 2 2019 Hide and seek with repetitions. Zbl 1410.68309Gawrychowski, Paweł; Manea, Florin; Mercaş, Robert; Nowotka, Dirk 2 2019 The complexity of synchronizing Markov decision processes. Zbl 1421.68099Doyen, Laurent; Massart, Thierry; Shirmohammadi, Mahsa 2 2019 Derivatives and partial derivatives for regular shuffle expressions. Zbl 1423.68267Sulzmann, Martin; Thiemann, Peter 2 2019 Colouring square-free graphs without long induced paths. Zbl 1429.68081Gaspers, Serge; Huang, Shenwei; Paulusma, Daniël 2 2019 Parameterized shifted combinatorial optimization. Zbl 1408.68075Gajarský, Jakub; Hliněný, Petr; Koutecký, Martin; Onn, Shmuel 1 2019 Path-contractions, edge deletions and connectivity preservation. Zbl 1412.68084Gutin, Gregory; Ramanujan, M. S.; Reidl, Felix; Wahlström, Magnus 1 2019 Recursion-theoretic ranking and compression. Zbl 1459.03059Hemaspaandra, Lane A.; Rubery, Daniel 1 2019 Computational capabilities of analog and evolving neural networks over infinite input streams. Zbl 1410.68120Cabessa, Jérémie; Finkel, Olivier 1 2019 Vector and scalar reachability problems in \(\operatorname{SL}(2, \mathbb{Z})\). Zbl 1421.68095Potapov, Igor; Semukhin, Pavel 1 2019 The complexity of routing with collision avoidance. Zbl 1421.68076Fluschnik, Till; Morik, Marco; Sorge, Manuel 1 2019 Finite-state independence and normal sequences. Zbl 1423.68239Álvarez, Nicolás; Becher, Verónica; Carton, Olivier 1 2019 A Nivat theorem for weighted picture automata and weighted MSO logics. Zbl 1423.68242Babari, Parvaneh; Droste, Manfred 1 2019 ...and 1378 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 23,760 Authors 127 Saurabh, Saket 113 Ibarra, Oscar H. 90 Jain, Sanjay 82 Niedermeier, Rolf 80 Fomin, Fedor V. 73 Kutrib, Martin 70 Stephan, Frank 65 Goldreich, Oded 64 Fernau, Henning 63 Engelfriet, Joost 61 Hemaspaandra, Lane A. 60 Golovach, Petr A. 57 Lokshtanov, Daniel 56 Epstein, Leah 56 Rozenberg, Grzegorz 55 Otto, Friedrich 55 Salomaa, Kai T. 54 Raman, Venkatesh 53 Ésik, Zoltán 53 Paschos, Vangelis Th. 53 Pelc, Andrzej 51 Vardi, Moshe Ya’akov 50 Gutin, Gregory Z. 50 Zehavi, Meirav 49 Pilipczuk, Marcin L. 48 Pilipczuk, Michał 48 Rytter, Wojciech 47 Holzer, Markus 46 Salomaa, Arto Kustaa 45 Cai, Jin-Yi 45 Courcelle, Bruno 45 Thilikos, Dimitrios M. 43 Demaine, Erik D. 42 Allender, Eric W. 42 Chen, Jian-er 42 Gottlob, Georg 42 Lohrey, Markus 42 Malcher, Andreas 42 Okhotin, Alexander 42 Pérez-Jiménez, Mario J. 41 Case, John 41 Rothe, Jörg-Matthias 41 Wood, Derick 40 Alon, Noga 40 Jansen, Bart M. P. 40 Szeider, Stefan 40 Wigderson, Avi 39 Marx, Dániel 37 Bose, Prosenjit K. 37 Fellows, Michael Ralph 37 Milius, Stefan 37 Pan, Linqiang 37 Păun, Gheorghe 36 Adámek, Jiří 36 Bodlaender, Hans L. 36 Chan, Timothy Moon-Yew 36 Italiano, Giuseppe Francesco 36 Komusiewicz, Christian 36 Mauri, Giancarlo 36 Papadimitriou, Christos Harilaos 36 Sharir, Micha 36 Spirakis, Paul G. 35 Crochemore, Maxime 35 Köbler, Johannes 35 Paulusma, Daniël 35 Peleg, David 35 Servedio, Rocco A. 34 Chatterjee, Krishnendu 34 Kratsch, Stefan 34 Sau, Ignasi 33 Fortnow, Lance J. 33 Hromkovič, Juraj 33 Monnot, Jérôme 33 Wang, Jianxin 32 Book, Ronald Vernon 32 Cygan, Marek 32 Jiang, Tao 32 Levin, Asaf 32 Navarro, Gonzalo 31 Culik, Karel II 31 Eiter, Thomas 31 Eppstein, David Arthur 31 Guo, Jiong 31 Heggernes, Pinar 31 Karhumaki, Juhani 31 Karpinski, Marek 31 Vollmer, Heribert 31 Woeginger, Gerhard 30 Arvind, Vikraman 30 Bshouty, Nader H. 30 Kanj, Iyad A. 30 Munro, J. Ian 30 Panolan, Fahad 30 Watanabe, Osamu 30 Yeo, Anders 30 Yu, Sheng 29 Lingas, Andrzej 29 Lutz, Jack H. 29 Mnich, Matthias 29 Thérien, Denis ...and 23,660 more Authors all top 5 Cited in 789 Journals 3,553 Theoretical Computer Science 1,554 Journal of Computer and System Sciences 1,057 Information Processing Letters 893 Algorithmica 794 Discrete Applied Mathematics 790 Information and Computation 405 Theory of Computing Systems 310 Information Sciences 307 International Journal of Foundations of Computer Science 281 Acta Informatica 253 Artificial Intelligence 246 SIAM Journal on Computing 223 Mathematical Systems Theory 206 Journal of Combinatorial Optimization 195 Computational Geometry 191 European Journal of Operational Research 182 Computational Complexity 151 Discrete & Computational Geometry 149 Discrete Mathematics 147 Annals of Pure and Applied Logic 144 International Journal of Computer Mathematics 141 Journal of Discrete Algorithms 137 Distributed Computing 136 Mathematical Programming. Series A. Series B 133 Journal of Cryptology 127 Machine Learning 126 SIAM Journal on Discrete Mathematics 122 Operations Research Letters 119 Annals of Mathematics and Artificial Intelligence 118 Logical Methods in Computer Science 112 Journal of Symbolic Computation 104 International Journal of Approximate Reasoning 95 Quantum Information Processing 91 RAIRO. Informatique Théorique et Applications 90 Combinatorica 90 RAIRO. Theoretical Informatics and Applications 85 Fuzzy Sets and Systems 84 MSCS. Mathematical Structures in Computer Science 82 Applied Mathematics and Computation 82 The Journal of Symbolic Logic 82 Journal of Complexity 82 Soft Computing 81 Computers & Operations Research 76 RAIRO, Informatique Théorique 72 Discrete Optimization 69 Computing 67 Annals of Operations Research 67 Pattern Recognition 65 International Journal of Computational Geometry & Applications 64 European Journal of Combinatorics 64 Formal Aspects of Computing 63 Random Structures & Algorithms 61 International Journal of Algebra and Computation 61 Natural Computing 60 Neural Computation 59 Journal of Automated Reasoning 57 Journal of Mathematical Analysis and Applications 57 Linear Algebra and its Applications 56 Journal of Logical and Algebraic Methods in Programming 52 Computers & Mathematics with Applications 52 Journal of Combinatorial Theory. Series B 52 Formal Methods in System Design 51 Networks 50 The Annals of Statistics 50 Journal of Scheduling 49 ACM Transactions on Computational Logic 49 Journal of Membrane Computing 48 Journal of Optimization Theory and Applications 48 Theory and Practice of Logic Programming 48 Journal of Machine Learning Research (JMLR) 47 International Journal of Theoretical Physics 47 Automatica 47 BIT 46 Computer Science Review 45 Mathematics of Computation 45 Designs, Codes and Cryptography 42 Combinatorics, Probability and Computing 40 Cybernetics 40 The Journal of Logic and Algebraic Programming 39 International Journal of Computer & Information Sciences 39 Mathematics of Operations Research 39 New Generation Computing 38 Journal of Algebra 38 Journal of Computer Science and Technology 38 Journal of Applied Logic 37 Journal of Applied Non-Classical Logics 37 Algorithms 36 Studia Logica 36 Cybernetics and Systems Analysis 36 Journal of Graph Algorithms and Applications 35 Computational Statistics and Data Analysis 35 Journal of Intelligent and Fuzzy Systems 34 Physica D 34 Journal of Logic, Language and Information 34 The Electronic Journal of Combinatorics 33 Semigroup Forum 33 Fundamenta Informaticae 32 Transactions of the American Mathematical Society 32 Mathematical Problems in Engineering 31 Journal of Soviet Mathematics ...and 689 more Journals all top 5 Cited in 62 Fields 18,626 Computer science (68-XX) 3,913 Combinatorics (05-XX) 2,776 Operations research, mathematical programming (90-XX) 2,632 Mathematical logic and foundations (03-XX) 1,500 Information and communication theory, circuits (94-XX) 1,200 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 747 Statistics (62-XX) 747 Numerical analysis (65-XX) 492 Biology and other natural sciences (92-XX) 462 Probability theory and stochastic processes (60-XX) 455 Quantum theory (81-XX) 447 Group theory and generalizations (20-XX) 367 Number theory (11-XX) 342 Systems theory; control (93-XX) 315 Convex and discrete geometry (52-XX) 306 Order, lattices, ordered algebraic structures (06-XX) 267 Linear and multilinear algebra; matrix theory (15-XX) 240 Dynamical systems and ergodic theory (37-XX) 220 Category theory; homological algebra (18-XX) 189 General algebraic systems (08-XX) 114 Statistical mechanics, structure of matter (82-XX) 113 Ordinary differential equations (34-XX) 113 Calculus of variations and optimal control; optimization (49-XX) 98 Field theory and polynomials (12-XX) 94 General topology (54-XX) 83 Algebraic geometry (14-XX) 82 Functional analysis (46-XX) 78 Commutative algebra (13-XX) 70 Associative rings and algebras (16-XX) 70 Approximations and expansions (41-XX) 70 Operator theory (47-XX) 64 Measure and integration (28-XX) 54 Geometry (51-XX) 51 History and biography (01-XX) 47 Partial differential equations (35-XX) 42 General and overarching topics; collections (00-XX) 36 Manifolds and cell complexes (57-XX) 34 Real functions (26-XX) 33 Harmonic analysis on Euclidean spaces (42-XX) 25 Functions of a complex variable (30-XX) 24 Integral equations (45-XX) 24 Algebraic topology (55-XX) 19 Global analysis, analysis on manifolds (58-XX) 19 Fluid mechanics (76-XX) 18 Differential geometry (53-XX) 16 Mechanics of particles and systems (70-XX) 16 Mechanics of deformable solids (74-XX) 15 Difference and functional equations (39-XX) 14 Topological groups, Lie groups (22-XX) 8 Geophysics (86-XX) 7 Special functions (33-XX) 7 Sequences, series, summability (40-XX) 7 Abstract harmonic analysis (43-XX) 7 Integral transforms, operational calculus (44-XX) 5 Optics, electromagnetic theory (78-XX) 4 Nonassociative rings and algebras (17-XX) 2 Potential theory (31-XX) 2 Several complex variables and analytic spaces (32-XX) 2 Relativity and gravitational theory (83-XX) 2 Astronomy and astrophysics (85-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Mathematics education (97-XX) Citations by Year