Journal of Computer and System Sciences Short Title: J. Comput. Syst. Sci. Publisher: Elsevier (Academic Press), San Diego, CA ISSN: 0022-0000 Online: https://www.sciencedirect.com/journal/journal-of-computer-and-system-sciences/issues Comments: Journal; Indexed cover-to-cover Documents Indexed: 3,143 Publications (since 1967) References Indexed: 2,870 Publications with 72,533 References. all top 5 Latest Issues 144 (2024) 143 (2024) 142 (2024) 141 (2024) 140 (2024) 139 (2024) 138 (2023) 137 (2023) 136 (2023) 135 (2023) 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) ...and 196 more Volumes all top 5 Authors 25 Papadimitriou, Christos Harilaos 24 Engelfriet, Joost 23 Jain, Sanjay 20 Fomin, Fedor V. 18 Niedermeier, Rolf 18 Saurabh, Saket 18 Ullman, Jeffrey David 17 Yannakakis, Mihalis 16 Rozenberg, Grzegorz 16 Stephan, Frank 15 Ibarra, Oscar H. 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 Cai, Jin-Yi 12 Galil, Zvi 12 Goldberg, Leslie Ann 12 Hemaspaandra, Lane A. 12 Vardi, Moshe Ya’akov 11 Case, John 11 Li, Ming 11 Reif, John H. 11 Salomaa, Arto Kustaa 11 Szeider, Stefan 11 Van Gucht, Dirk 10 Alon, Noga 10 Bshouty, Nader H. 10 Chen, Jian-er 10 Downey, Rodney Graham 10 Fortnow, Lance J. 10 Golovach, Petr A. 10 Hsieh, Sun-Yuan 10 Paulusma, Daniël 10 Pippenger, Nicholas J. 10 Spirakis, Paul G. 9 Bloom, Stephen L. 9 Epstein, Leah 9 Gąsieniec, Leszek Antoni 9 Goldman, Sally A. 9 Impagliazzo, Russell 9 Kolaitis, Phokion G. 9 Kowalski, Dariusz R. 9 Lipton, Richard Jay 9 Long, Philip M. 9 Lynch, Nancy Ann 9 McKenzie, Pierre 9 Milo, Tova 9 Sagiv, Yehoshua 9 Van den Bussche, Jan 8 Buhrman, Harry 8 Fagin, Ronald 8 Gyssens, Marc 8 Harel, David 8 Hartmanis, Juris 8 Kanj, Iyad A. 8 Karpinski, Marek 8 Klasing, Ralf 8 Libkin, Leonid O. 8 Maass, Wolfgang 8 Paterson, Mike S. 8 Rothe, Jörg-Matthias 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 Bartlett, Peter L. 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 Jansen, Bart M. P. 7 Jerrum, Mark R. 7 Jiang, Tao 7 Kleinberg, Jon Michael 7 Köbler, Johannes 7 Ladner, Richard E. 7 Li, Keqin 7 Ma, Bin 7 Mertzios, George B. 7 Ordyniak, Sebastian 7 Paredaens, Jan 7 Pnueli, Amir ...and 4,147 more Authors all top 5 Fields 2,866 Computer science (68-XX) 313 Mathematical logic and foundations (03-XX) 260 Combinatorics (05-XX) 151 Information and communication theory, circuits (94-XX) 149 Operations research, mathematical programming (90-XX) 88 General and overarching topics; collections (00-XX) 80 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) 29 Statistics (62-XX) 27 Probability theory and stochastic processes (60-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) 20 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) 2 Global analysis, analysis on manifolds (58-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 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,552 Publications have been cited 45,589 times in 30,564 Documents Cited by ▼ Year ▼ Which problems have strongly exponential complexity? Zbl 1006.68052 Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis 563 2001 A decision-theoretic generalization of on-line learning and an application to boosting. Zbl 0880.68103 Freund, Yoav; Schapire, Robert E. 540 1997 Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Zbl 0367.68034 Booth, Kellogg S.; Lueker, George S. 535 1976 Optimization, approximation, and complexity classes. Zbl 0765.68036 Papadimitriou, Christos H.; Yannakakis, Mihalis 532 1991 On the complexity of \(k\)-SAT. Zbl 0990.68079 Impagliazzo, Russell; Paturi, Ramamohan 459 2001 Approximation algorithms for combinatorial problems. Zbl 0296.65036 Johnson, David S. 457 1974 Computing with membranes. Zbl 0956.68055 Păun, Gheorghe 447 2000 Relationships between nondeterministic and deterministic tape complexities. Zbl 0188.33502 Savitch, W. J. 441 1970 Probabilistic encryption. Zbl 0563.94013 Goldwasser, Shafi; Micali, Silvio 429 1984 Universal classes of hash functions. Zbl 0412.68090 Carter, J. Lawrence; Wegman, Mark N. 306 1979 Variable precision rough set model. Zbl 0764.68162 Ziarko, Wojciech 292 1993 Propositional dynamic logic of regular programs. Zbl 0408.03014 Fischer, Michael J.; Ladner, Richard E. 291 1979 A data structure for dynamic trees. Zbl 0509.68058 Sleator, Daniel D.; Tarjan, Robert Endre 278 1983 Time bounds for selection. Zbl 0278.68033 Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E. 274 1973 The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029 Lewis, John M.; Yannakakis, Mihalis 260 1980 Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061 Khot, Subhash; Regev, Oded 256 2008 A theory of type polymorphism in programming. Zbl 0388.68003 Milner, Robin 255 1978 Hardness vs randomness. Zbl 0821.68057 Nisan, Noam; Wigderson, Avi 250 1994 On the computational power of pushdown automata. Zbl 0207.01701 Aho, A. V.; Ullman, J. D.; Hopcroft, J. E. 246 1970 On problems without polynomial kernels. Zbl 1192.68288 Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny 230 2009 Self-testing/correcting with applications to numerical problems. Zbl 0795.68131 Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt 229 1993 Parallel program schemata. Zbl 0198.32603 Karp, Richard M.; Miller, Raymond E. 219 1969 Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). Zbl 0667.68059 Barrington, David A. 219 1989 On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048 Papadimitriou, Christos H. 217 1994 The space complexity of approximating the frequency moments. Zbl 0938.68153 Alon, Noga; Matias, Yossi; Szegedy, Mario 199 1999 Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074 Yannakakis, Mihalis 194 1991 New hash functions and their use in authentication and set equality. Zbl 0461.68074 Wegman, Mark N.; Carter, J. Lawrence 190 1981 How easy is local search? Zbl 0655.68074 Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis 188 1988 Isomorphism of graphs of bounded valence can be tested in polynomial time. Zbl 0493.68064 Luks, Eugene M. 171 1982 A linear-time algorithm for a special case of disjoint set union. Zbl 0572.68058 Gabow, Harold N.; Tarjan, Robert Endre 170 1985 Optimization of LR(k) parsers. Zbl 0264.68032 Aho, A. V.; Ullman, J. D. 167 1972 Randomness is linear in space. Zbl 0846.68041 Nisan, Noam; Zuckerman, David 164 1996 Handle-rewriting hypergraph grammars. Zbl 0825.68446 Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz 162 1993 On uniform circuit complexity. Zbl 0462.68013 Ruzzo, Walter L. 162 1981 Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040 Achlioptas, Dimitris 159 2003 Fast probabilistic algorithms for Hamiltonian circuits and matchings. Zbl 0437.05040 Angluin, D.; Valiant, L. G. 159 1979 A faster algorithm computing string edit distances. Zbl 0436.68044 Masek, William J.; Paterson, Michael S. 151 1980 On the time-complexity of broadcast in multi-hop radio networks: An exponential gap between determinism and randomization. Zbl 0752.68009 Bar-Yehuda, Reuven; Goldreich, Oded; Itai, Alon 150 1992 Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029 Babai, László; Moran, Shlomo 149 1988 On uniformity within \(NC^ 1\). Zbl 0719.68023 Barrington, David A. Mix; Immerman, Neil; Straubing, Howard 148 1990 Finding patterns common to a set of strings. Zbl 0454.68108 Angluin, Dana 145 1980 Tree acceptors and some of their applications. Zbl 0212.02901 Doner, John 143 1970 Minimum disclosure proofs of knowledge. Zbl 0656.68109 Brassard, Gilles; Chaum, David; Crépeau, Claude 142 1988 The complexity of optimization problems. Zbl 0652.68040 Krentel, Mark W. 139 1988 A tight bound on approximating arbitrary metrics by tree metrics. Zbl 1071.68082 Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal 137 2004 An information statistics approach to data stream and communication complexity. Zbl 1074.68022 Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D. 136 2004 Maintenance of configurations in the plane. Zbl 0474.68082 Overmars, Mark H.; van Leeuwen, Jan 135 1981 Riemann’s hypothesis and tests for primality. Zbl 0349.68025 Miller, Gary L. 134 1976 Fast algorithms for bin packing. Zbl 0284.68023 Johnson, David S. 131 1974 Natural proofs. Zbl 0884.68055 Razborov, Alexander A.; Rudich, Steven 128 1997 Space-bounded reducibility among combinatorial problems. Zbl 0317.02039 Jones, Neil D. 125 1975 Making data structures persistent. Zbl 0667.68026 Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E. 125 1989 A framework for solving VLSI graph layout problems. Zbl 0543.68052 Bhatt, Sandeep N.; Leighton, Frank Thompson 123 1984 NP-complete scheduling problems. Zbl 0313.68054 Ullman, J. D. 122 1975 On the complexity of some two-person perfect-information games. Zbl 0383.90112 Schaefer, Thomas J. 121 1978 Structure and complexity of relational queries. Zbl 0511.68073 Chandra, Ashok; Harel, David 120 1982 The complexity of facets (and some facets of complexity). Zbl 0571.68028 Papadimitriou, C. H.; Yannakakis, M. 120 1984 Relaxing the uniformity and independence assumptions using the concept of fractal dimension. Zbl 0889.68050 Faloutsos, Christos; Kamel, Ibrahim 114 1997 Groups, the theory of ends, and context-free languages. Zbl 0537.20011 Muller, David E.; Schupp, Paul E. 114 1983 What’s decidable about hybrid automata? Zbl 0920.68091 Henzinger, Thomas A.; Kopke, Peter W.; Puri, Anuj; Varaiya, Pravin 113 1998 Semantics of probabilistic programs. Zbl 0476.68019 Kozen, Dexter 112 1981 Classifying regular events in symbolic logic. Zbl 0503.68055 Thomas, Wolfgang 112 1982 A lower bound for radio broadcast. Zbl 0753.68006 Alon, Noga; Bar-Noy, Amotz; Linial, Nathan; Peleg, David 111 1991 Probabilistic construction of deterministic algorithms: approximating packing integer programs. Zbl 0659.90066 Raghavan, Prabhakar 111 1988 Surpassing the information theoretic bound with fusion trees. Zbl 0795.68049 Fredman, Michael L.; Willard, Dan E. 109 1993 Reversal-bounded multipushdown machines. Zbl 0309.68043 Baker, Brenda S.; Book, Ronald V. 109 1974 Embedding planar graphs in four pages. Zbl 0673.05022 Yannakakis, Mihalis 105 1989 Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Zbl 0263.94019 Amoroso, S.; Patt, Y. N. 104 1972 Decision procedures and expressiveness in the temporal logic of branching time. Zbl 0559.68051 Emerson, E. Allen; Halpern, Joseph Y. 104 1985 Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144 Fortnow, Lance; Santhanam, Rahul 103 2011 A complete inference system for a class of regular behaviours. Zbl 0562.68065 Milner, Robin 103 1984 Automata-theoretic techniques for modal logics of programs. Zbl 0622.03017 Vardi, Moshe Y.; Wolper, Pierre 101 1986 Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045 Gabber, Ofer; Galil, Zvi 101 1981 Generalized sequential machine maps. Zbl 0198.03303 Thatcher, J. W. 100 1970 Topologically sweeping an arrangement. Zbl 0676.68013 Edelsbrunner, Herbert; Guibas, Leonidas J. 100 1989 Zero knowledge and the chromatic number. Zbl 0921.68089 Feige, Uriel; Kilian, Joe 98 1998 Faster shortest-path algorithms for planar graphs. Zbl 0880.68099 Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam 98 1997 Process complexity and effective random tests. Zbl 0273.68036 Schnorr, C. P. 98 1973 Classical complexity and quantum entanglement. Zbl 1093.81012 Gurvits, Leonid 96 2004 Conjunctive-query containment and constraint satisfaction. Zbl 0963.68059 Kolaitis, Phokion G.; Vardi, Moshe Y. 95 2000 Strong computational lower bounds via parameterized complexity. Zbl 1119.68092 Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge 94 2006 Multiattribute decision making models and methods using intuitionistic fuzzy sets. Zbl 1066.90052 Li, Deng-Feng 93 2005 Probabilistic counting algorithms for data base applications. Zbl 0583.68059 Flajolet, Philippe; Martin, G. Nigel 93 1985 Tesselations with local transformations. Zbl 0246.94037 Richardson, D. 90 1972 Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Zbl 0493.68043 Mahaney, Stephen R. 90 1982 Almost everywhere high nonuniform complexity. Zbl 0767.68043 Lutz, Jack H. 89 1992 Clustering with qualitative information. Zbl 1094.68075 Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony 89 2005 Varieties of ordered algebras. Zbl 0337.06008 Bloom, Stephen L. 89 1976 Pseudorandom generators without the XOR lemma. Zbl 1005.65006 Sudan, Madhu; Trevisan, Luca; Vadhan, Salil 86 2001 Computable queries for relational data bases. Zbl 0456.68128 Chandra, Ashok K.; Harel, David 86 1980 On the computational power of neural nets. Zbl 0826.68104 Siegelmann, Hava T.; Sontag, Eduardo D. 85 1995 Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Zbl 0155.01802 Thatcher, J. W. 85 1967 Linear unification. Zbl 0371.68013 Paterson, M. S.; Wegman, M. N. 85 1978 Power domains. Zbl 0391.68011 Smyth, M. B. 84 1978 Solving reflexive domain equations in a category of complete metric spaces. Zbl 0717.18002 America, Pierre; Rutten, Jan 84 1989 A constant-factor approximation algorithm for the \(k\)-median problem. Zbl 1023.90037 Charikar, Moses; Guha, Sudipto; Tardos, Éva; Shmoys, David B. 83 2002 Optimal shortest path queries in a simple polygon. Zbl 0681.68065 Guibas, Leonidas J.; Hershberger, John 83 1989 The average height of binary trees and other simple trees. Zbl 0499.68027 Flajolet, Philippe; Odlyzko, Andrew 81 1982 Threshold circuits of bounded depth. Zbl 0801.68052 Hajnal, András; Maass, Wolfgang; Pudlák, Pavel; Szegedy, Márió; Turán, György 81 1993 There are planar graphs almost as good as the complete graph. Zbl 0682.05032 Chew, L. Paul 81 1989 A near-linear kernel for bounded-state parsimony distance. Zbl 07783113 Deen, Elise; van Iersel, Leo; Janssen, Remie; Jones, Mark; Murakami, Yukihiro; Zeh, Norbert 1 2024 SAT backdoors: depth beats size. Zbl 07815426 Dreier, Jan; Ordyniak, Sebastian; Szeider, Stefan 1 2024 Mengerian graphs: characterization and recognition. Zbl 07753724 Ibiapina, Allen; Silva, Ana 1 2024 Deterministic non-adaptive contention resolution on a shared channel. Zbl 07639161 De Marco, Gianluca; Kowalski, Dariusz R.; Stachowiak, Grzegorz 3 2023 Balanced allocation on hypergraphs. Zbl 1529.90081 Greenhill, Catherine; Mans, Bernard; Pourmiri, Ali 2 2023 Grid recognition: classical and parameterized computational perspectives. Zbl 07695009 Gupta, Siddharth; Sa’ar, Guy; Zehavi, Meirav 2 2023 Succinct representation for (non)deterministic finite automata. Zbl 1497.68254 Chakraborty, Sankardeep; Grossi, Roberto; Sadakane, Kunihiko; Satti, Srinivasa Rao 1 2023 Parameterized complexity of multi-node hubs. Zbl 1529.68225 Saurabh, Saket; Zehavi, Meirav 1 2023 Complexity of verification in self-assembly with prebuilt assemblies. Zbl 07695008 Caballero, David; Gomez, Timothy; Schweller, Robert; Wylie, Tim 1 2023 Markov chains and unambiguous automata. Zbl 07695012 Baier, Christel; Kiefer, Stefan; Klein, Joachim; Müller, David; Worrell, James 1 2023 Galactic token sliding. Zbl 07695017 Bartier, Valentin; Bousquet, Nicolas; Mouawad, Amer E. 1 2023 Deletion to scattered graph classes. II: Improved FPT algorithms for deletion to pairs of graph classes. Zbl 1529.68216 Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh 1 2023 \(p\)-edge/vertex-connected vertex cover: parameterized and approximation algorithms. Zbl 07639162 Einarson, Carl; Gutin, Gregory; Jansen, Bart M. P.; Majumdar, Diptapriyo; Wahlström, Magnus 1 2023 A dichotomy for bounded degree graph homomorphisms with nonnegative weights. Zbl 07639675 Govorov, Artem; Cai, Jin-Yi; Dyer, Martin 1 2023 A physically universal Turing machine. Zbl 07639676 Salo, Ville; Törmä, Ilkka 1 2023 On finding separators in temporal split and permutation graphs. Zbl 07677364 Maack, Nicolas; Molter, Hendrik; Niedermeier, Rolf; Renken, Malte 1 2023 Orthogonal planarity testing of bounded treewidth graphs. Zbl 1533.68229 Di Giacomo, Emilio; Liotta, Giuseppe; Montecchiani, Fabrizio 11 2022 Refined notions of parameterized enumeration kernels with applications to matching cut enumeration. Zbl 1479.68002 Golovach, Petr A.; Komusiewicz, Christian; Kratsch, Dieter; Le, Van Bang 8 2022 Incompressibility of \(H\)-free edge modification problems: towards a dichotomy. Zbl 1533.68255 Marx, Dániel; Sandeep, R. B. 7 2022 Unlabeled sample compression schemes and corner peelings for ample and maximum classes. Zbl 1483.68281 Chalopin, Jérémie; Chepoi, Victor; Moran, Shay; Warmuth, Manfred K. 5 2022 Induced disjoint paths in AT-free graphs. Zbl 1478.68240 Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan 5 2022 Approximating the existential theory of the reals. Zbl 1533.91096 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 5 2022 Improved distance sensitivity oracles with subcubic preprocessing time. Zbl 1472.68119 Ren, Hanlin 4 2022 Medians in median graphs and their cube complexes in linear time. Zbl 1483.68250 Bénéteau, Laurine; Chalopin, Jérémie; Chepoi, Victor; Vaxès, Yann 4 2022 Word equations in non-deterministic linear space. Zbl 1472.68068 Jeż, Artur 3 2022 Complexity of fixed point counting problems in Boolean networks. Zbl 1483.68240 Bridoux, Florian; Durbec, Amélia; Perrot, Kevin; Richard, Adrien 3 2022 (In)approximability of maximum minimal FVS. Zbl 1478.68448 Dublois, Louis; Hanaka, Tesshu; Khosravian Ghadikolaei, Mehdi; Lampis, Michael; Melissinos, Nikolaos 3 2022 Scheduling lower bounds via AND subset sum. Zbl 1483.68142 Abboud, Amir; Bringmann, Karl; Hermelin, Danny; Shabtay, Dvir 3 2022 Complexity of stability. Zbl 1472.68113 Frei, Fabian; Hemaspaandra, Edith; Rothe, Jörg 2 2022 Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents. Zbl 1476.91070 Zhang, Hanrui 2 2022 Coloring temporal graphs. Zbl 1472.68117 Marino, Andrea; Silva, Ana 2 2022 Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs. Zbl 07526471 Brettell, Nick; Johnson, Matthew; Paulusma, Daniël 2 2022 Length-bounded cuts: proper interval graphs and structural parameters. Zbl 1505.68032 Bentert, Matthias; Heeger, Klaus; Knop, Dušan 2 2022 \(O_n\) is an \(n\)-MCFL. Zbl 1483.68169 Gebhardt, Kilian; Meunier, Frédéric; Salvati, Sylvain 2 2022 Complexity of the multilevel critical node problem. Zbl 1484.91085 Nabli, Adel; Carvalho, Margarida; Hosteins, Pierre 2 2022 Many-visits TSP revisited. Zbl 1478.68464 Kowalik, Łukasz; Li, Shaohua; Nadara, Wojciech; Smulewicz, Marcin; Wahlström, Magnus 2 2022 Approximate CVP\(_p\) in time \(2^{0.802n}\). Zbl 1478.68449 Eisenbrand, Friedrich; Venzin, Moritz 2 2022 An improved algorithm for the Steiner tree problem with bounded edge-length. Zbl 1472.68111 Chen, Chi-Yeh; Hsieh, Sun-Yuan 1 2022 Polynomial anonymous dynamic distributed computing without a unique leader. Zbl 1472.68116 Kowalski, Dariusz R.; Mosteiro, Miguel A. 1 2022 A \(4+\epsilon\) approximation for \(k\)-connected subgraphs. Zbl 1472.68215 Nutov, Zeev 1 2022 Non-essential arcs in phylogenetic networks. Zbl 07526468 Linz, Simone; Semple, Charles 1 2022 Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms. Zbl 1490.68120 Brand, Cornelius 1 2022 Dual domination problems in graphs. Zbl 07526469 Cordasco, Gennaro; Gargano, Luisa; Rescigno, Adele A. 1 2022 Cutting corners. Zbl 07526470 Salo, Ville 1 2022 Preprocessing vertex-deletion problems: characterizing graph properties by low-rank adjacencies. Zbl 1483.68258 Jansen, Bart M. P.; de Kroon, Jari J. H. 1 2022 Multistage knapsack. Zbl 1489.90147 Bampis, Evripidis; Escoffier, Bruno; Teiller, Alexandre 1 2022 On the threshold of intractability. Zbl 1478.68104 Drange, Pål Grønås; Dregi, Markus Fanebust; Lokshtanov, Daniel; Sullivan, Blair D. 1 2022 Polynomially ambiguous probabilistic automata on restricted languages. Zbl 1483.68156 Bell, Paul C. 1 2022 Intersection joins under updates. Zbl 1532.68012 Tao, Yufei; Yi, Ke 1 2022 Normalized information distance and the oscillation hierarchy. Zbl 1481.68031 Ambos-Spies, Klaus; Merkle, Wolfgang; Terwijn, Sebastiaan A. 1 2022 An extension of the Moran process using type-specific connection graphs. Zbl 1478.92160 Melissourgos, Themistoklis; Nikoletseas, Sotiris E.; Raptopoulos, Christoforos L.; Spirakis, Paul G. 1 2022 Fine-grained complexity of rainbow coloring and its variants. Zbl 1481.68033 Agrawal, Akanksha 1 2022 Efficiently enumerating hitting sets of hypergraphs arising in data profiling. Zbl 1478.68219 Bläsius, Thomas; Friedrich, Tobias; Lischeid, Julius; Meeks, Kitty; Schirneck, Martin 1 2022 The tree-generative capacity of combinatory categorial grammars. Zbl 1485.68130 Kuhlmann, Marco; Maletti, Andreas; Schiffer, Lena Katharina 1 2022 Greedy routing and the algorithmic small-world phenomenon. Zbl 1533.68011 Bringmann, Karl; Keusch, Ralph; Lengler, Johannes; Maus, Yannic; Molla, Anisur R. 1 2022 On temporal graph exploration. Zbl 1477.68222 Erlebach, Thomas; Hoffmann, Michael; Kammer, Frank 13 2021 Deleting edges to restrict the size of an epidemic in temporal networks. Zbl 1477.68221 Enright, Jessica; Meeks, Kitty; Mertzios, George B.; Zamaraev, Viktor 13 2021 The complexity of reachability in parametric Markov decision processes. Zbl 1477.68124 Junges, Sebastian; Katoen, Joost-Pieter; Pérez, Guillermo A.; Winkler, Tobias 13 2021 Sliding window temporal graph coloring. Zbl 1473.68123 Mertzios, George B.; Molter, Hendrik; Zamaraev, Viktor 11 2021 Assigning times to minimise reachability in temporal graphs. Zbl 1464.68283 Enright, Jessica; Meeks, Kitty; Skerman, Fiona 10 2021 Temporal cliques admit sparse spanners. Zbl 1517.68280 Casteigts, Arnaud; Peters, Joseph G.; Schoeters, Jason 10 2021 Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1477.68115 Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. 9 2021 The hairy ball problem is PPAD-complete. Zbl 1527.68082 Goldberg, Paul W.; Hollender, Alexandros 9 2021 The temporal explorer who returns to the base. Zbl 1515.68221 Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Raptopoulos, Christoforos 6 2021 Grammar-compressed indexes with logarithmic search time. Zbl 1477.68104 Claude, Francisco; Navarro, Gonzalo; Pacheco, Alejandro 6 2021 Exploration of dynamic networks: tight bounds on the number of agents. Zbl 1527.68024 Gotoh, Tsuyoshi; Flocchini, Paola; Masuzawa, Toshimitsu; Santoro, Nicola 6 2021 Preimage problems for deterministic finite automata. Zbl 1464.68148 Berlinkov, Mikhail V.; Ferens, Robert; Szykuła, Marek 4 2021 The complexity of the parity argument with potential. Zbl 1515.68243 Ishizuka, Takashi 4 2021 Measuring what matters: a hybrid approach to dynamic programming with treewidth. Zbl 1517.68291 Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Kwon, O-joung 4 2021 On the fast delivery problem with one or two packages. Zbl 1464.68278 Carvalho, Iago A.; Erlebach, Thomas; Papadopoulos, Kleitos 3 2021 A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion. Zbl 1482.68110 Donkers, Huib; Jansen, Bart M. P. 3 2021 Bivariate B-splines from convex configurations. Zbl 1531.65027 Schmitt, Dominique 3 2021 Understanding PPA-completeness. Zbl 1464.68121 Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying 2 2021 Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm. Zbl 1477.68133 Jones, Mark; Kelk, Steven; Stougie, Leen 2 2021 Reachability relations of timed pushdown automata. Zbl 1484.68079 Clemente, Lorenzo; Lasota, Sławomir 2 2021 When are emptiness and containment decidable for probabilistic automata? Zbl 1477.68150 Daviaud, Laure; Jurdziński, Marcin; Lazić, Ranko; Mazowiecki, Filip; Pérez, Guillermo A.; Worrell, James 2 2021 Bisection of bounded treewidth graphs by convolutions. Zbl 1477.68220 Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E. 2 2021 Reducing graph transversals via edge contractions. Zbl 1477.68239 Lima, Paloma T.; dos Santos, Vinicius F.; Sau, Ignasi; Souza, Uéverton S. 2 2021 Block trees. Zbl 1477.68076 Belazzougui, Djamal; Cáceres, Manuel; Gagie, Travis; Gawrychowski, Paweł; Kärkkäinen, Juha; Navarro, Gonzalo; Ordóñez, Alberto; Puglisi, Simon J.; Tabei, Yasuo 2 2021 On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Zbl 1480.91023 Caragiannis, Ioannis; Fanelli, Angelo 2 2021 Parameterized \(k\)-clustering: tractability island. Zbl 1477.68132 Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill 2 2021 Uniform parsing for hyperedge replacement grammars. Zbl 1482.68117 Björklund, Henrik; Drewes, Frank; Ericson, Petter; Starke, Florian 2 2021 Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. Zbl 1505.68018 Kozachinskiy, Alexander; Shen, Alexander 2 2021 A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem. Zbl 1480.68013 Li, Xingfu; Zhu, Daming; Wang, Lusheng 2 2021 An efficiently computable characterization of stability and instability for linear cellular automata. Zbl 1527.68136 Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano 2 2021 Lattice-based weak-key analysis on single-server outsourcing protocols of modular exponentiations and basic countermeasures. Zbl 1517.68107 Zheng, 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.68035 Zhao, Shuang; Chen, Zongqing; Yang, Weihua; Meng, Jixiang 1 2021 Equivalence of pushdown automata via first-order grammars. Zbl 1477.68153 Jančar, Petr 1 2021 Deciding the point-to-fixed-point problem for skew tent maps on an interval. Zbl 1470.37063 Kuijpers, Bart 1 2021 Deterministic protocols in the SINR model without knowledge of coordinates. Zbl 1467.68207 Moses, William K. jun.; Vaya, Shailesh 1 2021 Additive approximation algorithms for modularity maximization. Zbl 1477.68538 Kawase, Yasushi; Matsui, Tomomi; Miyauchi, Atsushi 1 2021 Bidding mechanisms in graph games. Zbl 1480.91053 Avni, Guy; Henzinger, Thomas A.; Žikelić, Đorđe 1 2021 Analytic methods for reachability problems. Zbl 1477.68159 Protasov, Vladimir Yu. 1 2021 Your rugby mates don’t need to know your colleagues: triadic closure with edge colors. Zbl 1477.68210 Bulteau, Laurent; Grüttemeier, Niels; Komusiewicz, Christian; Sorge, Manuel 1 2021 Algorithms for hierarchical and semi-partitioned parallel scheduling. Zbl 1479.90079 Bonifaci, Vincenzo; D’Angelo, Gianlorenzo; Marchetti-Spaccamela, Alberto 1 2021 Equivalence checking of quantum finite-state machines. Zbl 1511.68141 Wang, Qisheng; Liu, Junyi; Ying, Mingsheng 1 2021 Speeding-up verification of digital signatures. Zbl 1455.94193 Taleb, Abdul Rahman; Vergnaud, Damien 1 2021 Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem. Zbl 1477.68127 Lagerkvist, Victor; Roy, Biman 1 2021 Polynomial time approximation schemes for clustering in low highway dimension graphs. Zbl 1527.68260 Feldmann, Andreas Emil; Saulpic, David 1 2021 The complexity of finding small separators in temporal graphs. Zbl 1436.68265 Zschoche, Philipp; Fluschnik, Till; Molter, Hendrik; Niedermeier, Rolf 38 2020 ...and 1432 more Documents all cited Publications top 5 cited Publications all top 5 Cited by 27,664 Authors 167 Saurabh, Saket 129 Ibarra, Oscar H. 110 Fomin, Fedor V. 104 Kutrib, Martin 100 Niedermeier, Rolf 97 Jain, Sanjay 85 Golovach, Petr A. 81 Fernau, Henning 77 Stephan, Frank 74 Goldreich, Oded 74 Lokshtanov, Daniel 69 Raman, Venkatesh 66 Engelfriet, Joost 66 Pelc, Andrzej 65 Zehavi, Meirav 64 Salomaa, Kai T. 63 Epstein, Leah 63 Hemaspaandra, Lane A. 63 Otto, Friedrich 62 Wigderson, Avi 61 Rozenberg, Grzegorz 61 Vardi, Moshe Ya’akov 59 Ésik, Zoltán 59 Pilipczuk, Marcin L. 58 Thilikos, Dimitrios M. 57 Malcher, Andreas 57 Paschos, Vangelis Th. 57 Rytter, Wojciech 56 Cai, Jin-Yi 56 Gutin, Gregory Z. 55 Demaine, Erik D. 55 Holzer, Markus 55 Lohrey, Markus 54 Paulusma, Daniël 54 Pérez-Jiménez, Mario J. 52 Pilipczuk, Michał 51 Bodlaender, Hans L. 51 Szeider, Stefan 50 Alon, Noga 50 Komusiewicz, Christian 50 Spirakis, Paul G. 49 Allender, Eric W. 49 Chen, Jian-er 49 Rothe, Jörg-Matthias 48 Bose, Prosenjit K. 48 Marx, Dániel 48 Okhotin, Alexander 48 Servedio, Rocco A. 47 Gottlob, Georg 47 Jansen, Bart M. P. 47 Peleg, David 47 Salomaa, Arto Kustaa 46 Courcelle, Bruno 45 Case, John 45 Chatterjee, Krishnendu 45 Eppstein, David Arthur 45 Panolan, Fahad 44 Chan, Timothy Moon-Yew 44 Italiano, Giuseppe Francesco 44 Păun, Gheorghe 43 Pan, Linqiang 43 Papadimitriou, Christos Harilaos 43 Sau, Ignasi 42 Gawrychowski, Paweł 42 Kowalski, Dariusz R. 42 Milius, Stefan 42 Wang, Jianxin 42 Wood, Derick 41 Fellows, Michael Ralph 40 Lampis, Michael 40 Navarro, Gonzalo 39 Adámek, Jiří 39 Kociumaka, Tomasz 39 Lingas, Andrzej 39 Mauri, Giancarlo 39 Sharir, Micha 38 Crochemore, Maxime 38 Eiter, Thomas 38 Ito, Takehiro 38 Jiang, Tao 38 Karpinski, Marek 38 Levin, Asaf 38 Vadhan, Salil P. 37 Arvind, Vikraman 37 Heggernes, Pinar 37 Hromkovič, Juraj 37 Ishai, Yuval 37 Köbler, Johannes 37 Kratsch, Stefan 37 Munro, J. Ian 37 Williams, Richard Ryan 36 Ganian, Robert 36 Monnot, Jérôme 35 Bshouty, Nader H. 35 Fortnow, Lance J. 35 Otachi, Yota 35 Radoszewski, Jakub 35 Rauch Henzinger, Monika 35 Vollmer, Heribert 35 Woodruff, David P. ...and 27,564 more Authors all top 5 Cited in 847 Journals 3,746 Theoretical Computer Science 1,623 Journal of Computer and System Sciences 1,088 Information Processing Letters 992 Algorithmica 845 Discrete Applied Mathematics 841 Information and Computation 445 Theory of Computing Systems 387 Information Sciences 346 International Journal of Foundations of Computer Science 292 Acta Informatica 291 SIAM Journal on Computing 269 Artificial Intelligence 223 Mathematical Systems Theory 223 Journal of Combinatorial Optimization 209 Computational Geometry 206 European Journal of Operational Research 194 Computational Complexity 173 Discrete & Computational Geometry 163 Mathematical Programming. Series A. Series B 162 SIAM Journal on Discrete Mathematics 161 Logical Methods in Computer Science 158 Discrete Mathematics 154 Annals of Pure and Applied Logic 147 Distributed Computing 146 International Journal of Computer Mathematics 142 Journal of Discrete Algorithms 137 Journal of Cryptology 136 Machine Learning 135 Operations Research Letters 124 Annals of Mathematics and Artificial Intelligence 122 International Journal of Approximate Reasoning 120 Journal of Symbolic Computation 106 Quantum Information Processing 101 Fuzzy Sets and Systems 99 Natural Computing 98 Networks 95 Combinatorica 93 Mathematical Structures in Computer Science 91 RAIRO. Informatique Théorique et Applications 90 RAIRO. Theoretical Informatics and Applications 87 Random Structures & Algorithms 86 Applied Mathematics and Computation 86 Computers & Operations Research 85 The Journal of Symbolic Logic 84 Soft Computing 83 Journal of Complexity 76 RAIRO, Informatique Théorique 76 Discrete Optimization 71 European Journal of Combinatorics 70 Computing 70 International Journal of Computational Geometry & Applications 70 Journal of Machine Learning Research (JMLR) 69 Pattern Recognition 69 Journal of Logical and Algebraic Methods in Programming 68 Annals of Operations Research 68 Journal of Membrane Computing 66 International Journal of Algebra and Computation 66 ACM Transactions on Computational Logic 64 Journal of Automated Reasoning 64 Formal Aspects of Computing 64 Neural Computation 63 Linear Algebra and its Applications 58 Journal of Mathematical Analysis and Applications 58 Formal Methods in System Design 58 Journal of Scheduling 57 Computers & Mathematics with Applications 55 The Annals of Statistics 55 Journal of Combinatorial Theory. Series B 53 Automatica 51 Designs, Codes and Cryptography 51 Theory and Practice of Logic Programming 50 International Journal of Theoretical Physics 50 Journal of Graph Theory 49 Journal of Optimization Theory and Applications 49 Journal of the ACM 48 Journal of Graph Algorithms and Applications 48 Computer Science Review 47 BIT 46 The Journal of Logic and Algebraic Programming 45 Mathematics of Computation 45 Combinatorics, Probability and Computing 43 Journal of Algebra 43 Fundamenta Informaticae 42 Mathematics of Operations Research 40 Cybernetics 40 Journal of Global Optimization 40 ACM Journal of Experimental Algorithmics 39 International Journal of Computer & Information Sciences 39 Physica D 38 Journal of Computer Science and Technology 38 New Generation Computing 38 Neural Networks 38 Journal of Applied Non-Classical Logics 38 The Electronic Journal of Combinatorics 38 Journal of Applied Logic 38 Theory of Computing 37 Journal of Logic, Language and Information 36 Studia Logica 36 Computational Statistics and Data Analysis 36 Cybernetics and Systems Analysis ...and 747 more Journals all top 5 Cited in 63 Fields 23,356 Computer science (68-XX) 4,990 Combinatorics (05-XX) 3,384 Operations research, mathematical programming (90-XX) 3,119 Mathematical logic and foundations (03-XX) 2,106 Information and communication theory, circuits (94-XX) 1,512 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 944 Statistics (62-XX) 844 Numerical analysis (65-XX) 620 Quantum theory (81-XX) 584 Biology and other natural sciences (92-XX) 550 Probability theory and stochastic processes (60-XX) 540 Group theory and generalizations (20-XX) 448 Number theory (11-XX) 397 Systems theory; control (93-XX) 377 Order, lattices, ordered algebraic structures (06-XX) 360 Convex and discrete geometry (52-XX) 334 Linear and multilinear algebra; matrix theory (15-XX) 317 Dynamical systems and ergodic theory (37-XX) 261 Category theory; homological algebra (18-XX) 213 General algebraic systems (08-XX) 146 Statistical mechanics, structure of matter (82-XX) 131 Ordinary differential equations (34-XX) 125 Calculus of variations and optimal control; optimization (49-XX) 114 Field theory and polynomials (12-XX) 112 General topology (54-XX) 104 Functional analysis (46-XX) 102 Algebraic geometry (14-XX) 86 Commutative algebra (13-XX) 83 Operator theory (47-XX) 79 Approximations and expansions (41-XX) 77 Associative rings and algebras (16-XX) 72 Measure and integration (28-XX) 62 History and biography (01-XX) 61 Geometry (51-XX) 56 Partial differential equations (35-XX) 49 General and overarching topics; collections (00-XX) 44 Manifolds and cell complexes (57-XX) 40 Real functions (26-XX) 39 Harmonic analysis on Euclidean spaces (42-XX) 30 Functions of a complex variable (30-XX) 30 Algebraic topology (55-XX) 24 Integral equations (45-XX) 23 Global analysis, analysis on manifolds (58-XX) 23 Mechanics of particles and systems (70-XX) 23 Fluid mechanics (76-XX) 22 Differential geometry (53-XX) 20 Mechanics of deformable solids (74-XX) 16 Topological groups, Lie groups (22-XX) 14 Difference and functional equations (39-XX) 11 Relativity and gravitational theory (83-XX) 10 Geophysics (86-XX) 9 Special functions (33-XX) 9 Abstract harmonic analysis (43-XX) 8 Integral transforms, operational calculus (44-XX) 7 Sequences, series, summability (40-XX) 6 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 Astronomy and astrophysics (85-XX) 1 \(K\)-theory (19-XX) 1 Classical thermodynamics, heat transfer (80-XX) 1 Mathematics education (97-XX) Citations by Year