## 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,048 Publications (since 1967) References Indexed: 2,775 Publications with 68,902 References.
all top 5

### Latest Issues

 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) 76, No. 2 (2010) 76, No. 1 (2010) 75, No. 8 (2009) 75, No. 7 (2009) 75, No. 6 (2009) 75, No. 5 (2009) ...and 180 more Volumes
all top 5

### Authors

 25 Papadimitriou, Christos Harilaos 24 Engelfriet, Joost 22 Jain, Sanjay 18 Ullman, Jeffrey David 17 Yannakakis, Mihalis 16 Fomin, Fedor V. 16 Rozenberg, Grzegorz 15 Ibarra, Oscar H. 15 Niedermeier, Rolf 15 Stephan, Frank 14 Fellows, Michael Ralph 14 Ginsburg, Seymour 14 Saurabh, Saket 13 Greibach, Sheila A. 13 Vianu, Victor 12 Abiteboul, Serge 12 Allender, Eric W. 12 Galil, Zvi 12 Goldberg, Leslie Ann 12 Gutin, Gregory Z. 12 Hemaspaandra, Lane A. 12 Vardi, Moshe Ya’akov 11 Case, John 11 Reif, John H. 11 Salomaa, Arto Kustaa 11 Van Gucht, Dirk 10 Alon, Noga M. 10 Bshouty, Nader H. 10 Cai, Jin-Yi 10 Chen, Jian-er 10 Downey, Rodney Graham 10 Fortnow, Lance J. 10 Pippenger, Nicholas J. 9 Bloom, Stephen L. 9 Goldman, Sally A. 9 Impagliazzo, Russell 9 Kolaitis, Phokion G. 9 Lipton, Richard J. 9 Lynch, Nancy Ann 9 McKenzie, Pierre 9 Milo, Tova 9 Paulusma, Daniël 9 Sagiv, Yehoshua 9 Spirakis, Paul G. 9 Van den Bussche, Jan 8 Buhrman, Harry 8 Epstein, Leah 8 Fagin, Ronald 8 Golovach, Petr A. 8 Gyssens, Marc 8 Harel, David 8 Hartmanis, Juris 8 Hsieh, Sun-Yuan 8 Karpinski, Marek 8 Libkin, Leonid O. 8 Long, Philip M. 8 Maass, Wolfgang 8 Saks, Michael E. 8 Servedio, Rocco A. 8 Suciu, Dan Mircea 8 Szeider, Stefan 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 Gąsieniec, Leszek Antoni 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 Kanj, Iyad A. 7 Kleinberg, Jon Michael 7 Köbler, Johannes 7 Kowalski, Dariusz R. 7 Ladner, Richard E. 7 Ma, Bin 7 Paredaens, Jan 7 Pnueli, Amir 7 Raghavan, Prabhakar 7 Rothe, Jörg-Matthias 7 Selman, Alan L. 7 Spanier, Edwin Henry 7 Srinivasan, Aravind 7 Takizawa, Makoto 7 Taniar, David 7 Tarjan, Robert Endre 7 Wang, Lusheng ...and 3,965 more Authors
all top 5

### Fields

 2,770 Computer science (68-XX) 310 Mathematical logic and foundations (03-XX) 252 Combinatorics (05-XX) 148 Information and communication theory, circuits (94-XX) 142 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) 30 Number theory (11-XX) 29 Category theory; homological algebra (18-XX) 26 Probability theory and stochastic processes (60-XX) 26 Statistics (62-XX) 24 Systems theory; control (93-XX) 23 Quantum theory (81-XX) 21 Linear and multilinear algebra; matrix theory (15-XX) 20 Order, lattices, ordered algebraic structures (06-XX) 17 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)

### Citations contained in zbMATH Open

2,374 Publications have been cited 33,993 times in 23,050 Documents Cited by Year
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms. Zbl 0367.68034
Booth, Kellogg S.; Lueker, George S.
1976
A decision-theoretic generalization of on-line learning and an application to boosting. Zbl 0880.68103
Freund, Yoav; Schapire, Robert E.
1997
Optimization, approximation, and complexity classes. Zbl 0765.68036
1991
Which problems have strongly exponential complexity? Zbl 1006.68052
Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
2001
Approximation algorithms for combinatorial problems. Zbl 0296.65036
Johnson, David S.
1974
Relationships between nondeterministic and deterministic tape complexities. Zbl 0188.33502
Savitch, W. J.
1970
Computing with membranes. Zbl 0956.68055
Păun, Gheorghe
2000
Probabilistic encryption. Zbl 0563.94013
Goldwasser, Shafi; Micali, Silvio
1984
On the complexity of $$k$$-SAT. Zbl 0990.68079
Impagliazzo, Russell; Paturi, Ramamohan
2001
On the computational power of pushdown automata. Zbl 0207.01701
Aho, A. V.; Ullman, J. D.; Hopcroft, J. E.
1970
Propositional dynamic logic of regular programs. Zbl 0408.03014
Fischer, Michael J.; Ladner, Richard E.
1979
Time bounds for selection. Zbl 0278.68033
Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E.
1973
Variable precision rough set model. Zbl 0764.68162
Ziarko, Wojciech
1993
Universal classes of hash functions. Zbl 0412.68090
Carter, J. Lawrence; Wegman, Mark N.
1979
A theory of type polymorphism in programming. Zbl 0388.68003
Milner, Robin
1978
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
2009
A data structure for dynamic trees. Zbl 0509.68058
Sleator, Daniel D.; Tarjan, Robert Endre
1983
Parallel program schemata. Zbl 0198.32603
Karp, Richard M.; Miller, Raymond E.
1969
The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029
Lewis, John M.; Yannakakis, Mihalis
1980
Bounded-width polynomial-size branching programs recognize exactly those languages in $$NC^ 1$$. Zbl 0667.68059
Barrington, David A.
1989
Vertex cover might be hard to approximate to within $$2 - \varepsilon$$. Zbl 1133.68061
Khot, Subhash; Regev, Oded
2008
Optimization of LR(k) parsers. Zbl 0264.68032
Aho, A. V.; Ullman, J. D.
1972
Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074
Yannakakis, Mihalis
1991
Hardness vs randomness. Zbl 0821.68057
Nisan, Noam; Wigderson, Avi
1994
Self-testing/correcting with applications to numerical problems. Zbl 0795.68131
Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt
1993
Fast probabilistic algorithms for Hamiltonian circuits and matchings. Zbl 0437.05040
Angluin, D.; Valiant, L. G.
1979
Handle-rewriting hypergraph grammars. Zbl 0825.68446
Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz
1993
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
1988
A linear-time algorithm for a special case of disjoint set union. Zbl 0572.68058
Gabow, Harold N.; Tarjan, Robert Endre
1985
On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048
1994
Finding patterns common to a set of strings. Zbl 0454.68108
Angluin, Dana
1980
On uniform circuit complexity. Zbl 0462.68013
Ruzzo, Walter L.
1981
Isomorphism of graphs of bounded valence can be tested in polynomial time. Zbl 0493.68064
Luks, Eugene M.
1982
Tree acceptors and some of their applications. Zbl 0212.02901
Doner, John
1970
New hash functions and their use in authentication and set equality. Zbl 0461.68074
Wegman, Mark N.; Carter, J. Lawrence
1981
NP-complete scheduling problems. Zbl 0313.68054
Ullman, J. D.
1975
The complexity of optimization problems. Zbl 0652.68040
Krentel, Mark W.
1988
A faster algorithm computing string edit distances. Zbl 0436.68044
Masek, William J.; Paterson, Michael S.
1980
The space complexity of approximating the frequency moments. Zbl 0938.68153
Alon, Noga; Matias, Yossi; Szegedy, Mario
1999
Fast algorithms for bin packing. Zbl 0284.68023
Johnson, David S.
1974
On uniformity within $$NC^ 1$$. Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
1990
What’s decidable about hybrid automata? Zbl 0920.68091
Henzinger, Thomas A.; Kopke, Peter W.; Puri, Anuj; Varaiya, Pravin
1998
Space-bounded reducibility among combinatorial problems. Zbl 0317.02039
Jones, Neil D.
1975
Structure and complexity of relational queries. Zbl 0511.68073
Chandra, Ashok; Harel, David
1982
Relaxing the uniformity and independence assumptions using the concept of fractal dimension. Zbl 0889.68050
Faloutsos, Christos; Kamel, Ibrahim
1997
Maintenance of configurations in the plane. Zbl 0474.68082
Overmars, Mark H.; van Leeuwen, Jan
1981
Reversal-bounded multipushdown machines. Zbl 0309.68043
Baker, Brenda S.; Book, Ronald V.
1974
Riemann’s hypothesis and tests for primality. Zbl 0349.68025
Miller, Gary L.
1976
The complexity of facets (and some facets of complexity). Zbl 0571.68028
1984
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040
Achlioptas, Dimitris
2003
Classifying regular events in symbolic logic. Zbl 0503.68055
Thomas, Wolfgang
1982
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029
Babai, László; Moran, Shlomo
1988
A framework for solving VLSI graph layout problems. Zbl 0543.68052
Bhatt, Sandeep N.; Leighton, Frank Thompson
1984
Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Zbl 0263.94019
Amoroso, S.; Patt, Y. N.
1972
Marked directed graphs. Zbl 0238.05109
Commoner, F.; Holt, A. W.; Even, S.; Pnueli, A.
1971
Groups, the theory of ends, and context-free languages. Zbl 0537.20011
Muller, David E.; Schupp, Paul E.
1983
Process complexity and effective random tests. Zbl 0273.68036
Schnorr, C. P.
1973
A complete inference system for a class of regular behaviours. Zbl 0562.68065
Milner, Robin
1984
Probabilistic construction of deterministic algorithms: approximating packing integer programs. Zbl 0659.90066
Raghavan, Prabhakar
1988
Generalized sequential machine maps. Zbl 0198.03303
Thatcher, J. W.
1970
Making data structures persistent. Zbl 0667.68026
Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E.
1989
On the complexity of some two-person perfect-information games. Zbl 0383.90112
Schaefer, Thomas J.
1978
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Zbl 0493.68043
Mahaney, Stephen R.
1982
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
1992
On the complexity of teaching. Zbl 0939.68770
Goldman, Sally A.; Kearns, Michael J.
1995
Computable queries for relational data bases. Zbl 0456.68128
Chandra, Ashok K.; Harel, David
1980
In search of an easy witness: Exponential time vs. probabilistic polynomial time. Zbl 1059.68047
Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi
2002
A tight bound on approximating arbitrary metrics by tree metrics. Zbl 1071.68082
Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal
2004
Multiattribute decision making models and methods using intuitionistic fuzzy sets. Zbl 1066.90052
Li, Deng-Feng
2005
Topologically sweeping an arrangement. Zbl 0676.68013
Edelsbrunner, Herbert; Guibas, Leonidas J.
1989
Decision procedures and expressiveness in the temporal logic of branching time. Zbl 0559.68051
Emerson, E. Allen; Halpern, Joseph Y.
1985
Randomness is linear in space. Zbl 0846.68041
Nisan, Noam; Zuckerman, David
1996
Almost everywhere high nonuniform complexity. Zbl 0767.68043
Lutz, Jack H.
1992
Minimum disclosure proofs of knowledge. Zbl 0656.68109
Brassard, Gilles; Chaum, David; Crépeau, Claude
1988
Tesselations with local transformations. Zbl 0246.94037
Richardson, D.
1972
Boasson, Luc; Nivat, Maurice
1980
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
2011
Zero knowledge and the chromatic number. Zbl 0921.68089
Feige, Uriel; Kilian, Joe
1998
Linear unification. Zbl 0371.68013
Paterson, M. S.; Wegman, M. N.
1978
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045
Gabber, Ofer; Galil, Zvi
1981
An information statistics approach to data stream and communication complexity. Zbl 1074.68022
Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
2004
Automata-theoretic techniques for modal logics of programs. Zbl 0622.03017
Vardi, Moshe Y.; Wolper, Pierre
1986
Natural proofs. Zbl 0884.68055
Razborov, Alexander A.; Rudich, Steven
1997
Surpassing the information theoretic bound with fusion trees. Zbl 0795.68049
Fredman, Michael L.; Willard, Dan E.
1993
Conjunctive-query containment and constraint satisfaction. Zbl 0963.68059
Kolaitis, Phokion G.; Vardi, Moshe Y.
2000
Varieties of ordered algebras. Zbl 0337.06008
Bloom, Stephen L.
1976
Tree-size bounded alternation. Zbl 0445.68034
Ruzzo, Walter L.
1980
The average height of binary trees and other simple trees. Zbl 0499.68027
Flajolet, Philippe; Odlyzko, Andrew
1982
Power domains. Zbl 0391.68011
Smyth, M. B.
1978
Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Zbl 0155.01802
Thatcher, J. W.
1967
Solving reflexive domain equations in a category of complete metric spaces. Zbl 0717.18002
America, Pierre; Rutten, Jan
1989
Teaching a smarter learner. Zbl 1152.68451
Goldman, Sally A.; Mathias, H. David
1996
On the computational power of neural nets. Zbl 0826.68104
Siegelmann, Hava T.; Sontag, Eduardo D.
1995
Reversibility and surjectivity problems of cellular automata. Zbl 0802.68090
Kari, Jarkko
1994
The dot-depth hierarchy of star-free languages is infinite. Zbl 0368.68074
Brzozowski, J. A.; Knast, R.
1978
Real-time language recognition by one-dimensional cellular automata. Zbl 0268.68044
Smith, Alvy Ray III
1972
Structure preserving reductions among convex optimization problems. Zbl 0441.68049
Ausiello, G.; D’Atri, A.; Protasi, M.
1980
Probabilistic counting algorithms for data base applications. Zbl 0583.68059
Flajolet, Philippe; Martin, G. Nigel
1985
Embedding planar graphs in four pages. Zbl 0673.05022
Yannakakis, Mihalis
1989
Time bounded random access machines. Zbl 0284.68038
Cook, Stephen A.; Reckhow, Robert A.
1973
Multistage knapsack. Zbl 07499482
Bampis, Evripidis; Escoffier, Bruno; Teiller, Alexandre
2022
The complexity of reachability in parametric Markov decision processes. Zbl 1477.68124
Junges, Sebastian; Katoen, Joost-Pieter; Pérez, Guillermo A.; Winkler, Tobias
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
2021
Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. Zbl 1477.68115
Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G.
2021
Assigning times to minimise reachability in temporal graphs. Zbl 1464.68283
Enright, Jessica; Meeks, Kitty; Skerman, Fiona
2021
On temporal graph exploration. Zbl 1477.68222
Erlebach, Thomas; Hoffmann, Michael; Kammer, Frank
2021
Sliding window temporal graph coloring. Zbl 1473.68123
Mertzios, George B.; Molter, Hendrik; Zamaraev, Viktor
2021
Temporal cliques admit sparse spanners. Zbl 07368158
Casteigts, Arnaud; Peters, Joseph G.; Schoeters, Jason
2021
The Hairy Ball problem is PPAD-complete. Zbl 07396417
Goldberg, Paul W.; Hollender, Alexandros
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
2021
On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Zbl 1480.91023
Caragiannis, Ioannis; Fanelli, Angelo
2021
Parameterized $$k$$-clustering: tractability island. Zbl 1477.68132
Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill
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
2021
Deterministic protocols in the SINR model without knowledge of coordinates. Zbl 1467.68207
Moses, William K. jun.; Vaya, Shailesh
2021
Understanding PPA-completeness. Zbl 1464.68121
Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying
2021
Preimage problems for deterministic finite automata. Zbl 1464.68148
Berlinkov, Mikhail V.; Ferens, Robert; Szykuła, Marek
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
2021
Bisection of bounded treewidth graphs by convolutions. Zbl 1477.68220
Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E.
2021
A Turing kernelization dichotomy for structural parameterizations of $$\mathcal{F}$$-minor-free deletion. Zbl 1482.68110
Donkers, Huib; Jansen, Bart M. P.
2021
Measuring what matters: a hybrid approach to dynamic programming with treewidth. Zbl 07368162
Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Kwon, O-joung
2021
The complexity of finding small separators in temporal graphs. Zbl 1436.68265
Zschoche, Philipp; Fluschnik, Till; Molter, Hendrik; Niedermeier, Rolf
2020
Temporal vertex cover with a sliding time window. Zbl 1436.68219
Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Zamaraev, Viktor
2020
Graphs are not universal for online computability. Zbl 1476.03046
Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel
2020
2-D Tucker is PPA complete. Zbl 1436.68127
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
2020
Unique end of potential line. Zbl 1461.68086
Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul
2020
On Weisfeiler-Leman invariance: subgraph counts and related graph properties. Zbl 1450.05056
Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg
2020
Counting and enumerating tree-child networks and their subclasses. Zbl 1448.92147
Cardona, Gabriel; Zhang, Louxin
2020
Subexponential algorithms for variants of the homomorphism problem in string graphs. Zbl 1435.68243
Okrasa, Karolina; Rzążewski, Paweł
2020
Eccentricity terrain of $$\delta$$-hyperbolic graphs. Zbl 1450.05017
Dragan, Feodor F.; Guarnera, Heather M.
2020
How fast can we reach a target vertex in stochastic temporal graphs? Zbl 1456.68124
Akrida, Eleni C.; Mertzios, George B.; Nikoletseas, Sotiris; Raptopoulos, Christoforos; Spirakis, Paul G.; Zamaraev, Viktor
2020
Vulnerability of super extra edge-connected graphs. Zbl 1436.68225
Cheng, Chia-Wen; Hsieh, Sun-Yuan; Klasing, Ralf
2020
Clique-width and well-quasi-ordering of triangle-free graph classes. Zbl 1442.05184
2020
Complexity of control in judgment aggregation for uniform premise-based quota rules. Zbl 1448.91100
Baumeister, Dorothea; Erdélyi, Gábor; Erdélyi, Olivia J.; Rothe, Jörg; Selker, Ann-Kathrin
2020
LR-drawings of ordered rooted binary trees and near-linear area drawings of outerplanar graphs. Zbl 1436.68236
Frati, Fabrizio; Patrignani, Maurizio; Roselli, Vincenzo
2020
Hitting minors on bounded treewidth graphs. III. Lower bounds. Zbl 1435.68121
Baste, Julien; Sau, Ignasi; Thilikos, Dimitrios M.
2020
De Marco, Gianluca; Jurdziński, Tomasz; Kowalski, Dariusz R.; Różański, Michał; Stachowiak, Grzegorz
2020
Deciding probabilistic bisimilarity distance one for probabilistic automata. Zbl 1432.68247
Tang, Qiyi; van Breugel, Franck
2020
Online bin packing with cardinality constraints resolved. Zbl 1442.68269
Balogh, János; Békési, József; Dósa, György; Epstein, Leah; Levin, Asaf
2020
Disconnected cuts in claw-free graphs. Zbl 1450.05073
Martin, Barnaby; Paulusma, Daniël; van Leeuwen, Erik Jan
2020
A counterexample to Thiagarajan’s conjecture on regular event structures. Zbl 1442.68131
Chalopin, Jérémie; Chepoi, Victor
2020
An improved algorithm for the minmax regret path center problem on trees. Zbl 1446.68126
Wang, Biing-Feng; Ye, Jhih-Hong; Li, Chih-Yu
2020
Space efficient representations of finite groups. Zbl 1461.68061
Das, Bireswar; Sharma, Shivdutt; Vaidyanathan, P. R.
2020
The complexity of planar Boolean #CSP with complex weights. Zbl 1436.68135
Guo, Heng; Williams, Tyson
2020
On decidability and complexity of low-dimensional robot games. Zbl 1436.91002
Niskanen, R.; Potapov, I.; Reichert, J.
2020
On the degrees of non-regularity and non-context-freeness. Zbl 1447.68006
Bordihn, Henning; Mitrana, Victor
2020
Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence. Zbl 1435.68169
Jančar, Petr
2020
Boolean approximate counting CSPs with weak conservativity, and implications for ferromagnetic two-spin. Zbl 1435.68221
Backens, Miriam; Bulatov, Andrei; Goldberg, Leslie Ann; McQuillan, Colin; Živný, Stanislav
2020
The complexity of synthesizing elementary net systems relative to natural parameters. Zbl 1435.68214
Rosenke, Christian; Tredup, Ronny
2020
On the transformation capability of feasible mechanisms for programmable matter. Zbl 1421.68158
Michail, Othon; Skretas, George; Spirakis, Paul G.
2019
Temporal flows in temporal networks. Zbl 1423.68324
Akrida, Eleni C.; Czyzowicz, Jurek; Gąsieniec, Leszek; Kuszner, Łukasz; Spirakis, Paul G.
2019
Parameterized aspects of triangle enumeration. Zbl 1430.68176
Bentert, Matthias; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf
2019
A game characterisation of tree-like Q-resolution size. Zbl 1425.03028
Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek
2019
Bounding clique-width via perfect graphs. Zbl 1428.05220
Dabrowski, Konrad K.; Huang, Shenwei; Paulusma, Daniël
2019
Complexity of road coloring with prescribed reset words. Zbl 1425.68236
2019
On notions of distortion and an almost minimum spanning tree with constant average distortion. Zbl 1423.68326
Bartal, Yair; Filtser, Arnold; Neiman, Ofer
2019
The optimal absolute ratio for online bin packing. Zbl 1421.68238
Balogh, János; Békési, József; Dósa, György; Sgall, Jiří; van Stee, Rob
2019
Packet latency of deterministic broadcasting in adversarial multiple access channels. Zbl 1408.94922
Anantharamu, Lakshmi; Chlebus, Bogdan S.; Kowalski, Dariusz R.; Rokicki, Mariusz A.
2019
Structural sparsity of complex networks: bounded expansion in random models and real-world graphs. Zbl 1425.05149
Demaine, Erik D.; Reidl, Felix; Rossmanith, Peter; F. S. Sánchez Villaamil, Fernando; Sikdar, Somnath; Sullivan, Blair D.
2019
Colouring square-free graphs without long induced paths. Zbl 1429.68081
Gaspers, Serge; Huang, Shenwei; Paulusma, Daniël
2019
Hide and seek with repetitions. Zbl 1410.68309
Gawrychowski, Paweł; Manea, Florin; Mercaş, Robert; Nowotka, Dirk
2019
Copyless cost-register automata: structure, expressiveness, and closure properties. Zbl 1421.68050
Mazowiecki, Filip; Riveros, Cristian
2019
Finite-state independence and normal sequences. Zbl 1423.68239
Álvarez, Nicolás; Becher, Verónica; Carton, Olivier
2019
A Nivat theorem for weighted picture automata and weighted MSO logics. Zbl 1423.68242
Babari, Parvaneh; Droste, Manfred
2019
Insertion operations on deterministic reversal-bounded counter machines. Zbl 1423.68250
Eremondi, Joey; Ibarra, Oscar H.; McQuillan, Ian
2019
Classifying invariant structures of step traces. Zbl 1423.68310
Janicki, Ryszard; Kleijn, Jetty; Koutny, Maciej; Mikulski, Łukasz
2019
Calculi for symmetric queries. Zbl 1423.68139
Gyssens, Marc; Hellings, Jelle; Paredaens, Jan; Van Gucht, Dirk; Wijsen, Jef; Wu, Yuqing
2019
Fault-tolerant embedding of starlike trees into restricted hypercube-like graphs. Zbl 1423.68355
Park, Jung-Heum; Lim, Hyeong-Seok; Kim, Hee-Chul
2019
$$k$$-majority digraphs and the hardness of voting with a constant number of voters. Zbl 1427.91122
Bachmeier, Georg; Brandt, Felix; Geist, Christian; Harrenstein, Paul; Kardel, Keyvan; Peters, Dominik; Seedig, Hans Georg
2019
Deterministic rendezvous with different maps. Zbl 1439.68029
Farrugia, Ashley; Gąsieniec, Leszek; Kuszner, Łukasz; Pacheco, Eduardo
2019
Does adding more agents make a difference? A case study of cover time for the rotor-router. Zbl 1429.68311
2019
The complexity of routing with collision avoidance. Zbl 1421.68076
Fluschnik, Till; Morik, Marco; Sorge, Manuel
2019
HV-planarity: algorithms and complexity. Zbl 1409.68211
Didimo, Walter; Liotta, Giuseppe; Patrignani, Maurizio
2019
Path-contractions, edge deletions and connectivity preservation. Zbl 1412.68084
Gutin, Gregory; Ramanujan, M. S.; Reidl, Felix; Wahlström, Magnus
2019
Recursion-theoretic ranking and compression. Zbl 1459.03059
Hemaspaandra, Lane A.; Rubery, Daniel
2019
Computational capabilities of analog and evolving neural networks over infinite input streams. Zbl 1410.68120
Cabessa, Jérémie; Finkel, Olivier
2019
Reconfiguration in bounded bandwidth and tree-depth. Zbl 1382.68183
Wrochna, Marcin
2018
The relationship between extra connectivity and conditional diagnosability of regular graphs under the PMC model. Zbl 1390.68506
Lin, Limei; Hsieh, Sun-Yuan; Xu, Li; Zhou, Shuming; Chen, Riqing
2018
A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees. Zbl 1400.92379
Shi, Feng; Chen, Jianer; Feng, Qilong; Wang, Jianxin
2018
On discrete preferences and coordination. Zbl 1408.91041
Chierichetti, Flavio; Kleinberg, Jon; Oren, Sigal
2018
Towards a unified complexity theory of total functions. Zbl 1393.68053
Goldberg, Paul W.; Papadimitriou, Christos H.
2018
SOS specifications for uniformly continuous operators. Zbl 1380.68296
Gebler, Daniel; Tini, Simone
2018
Reconfiguration on sparse graphs. Zbl 1390.68351
Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket
2018
Range-max queries on uncertain data. Zbl 1390.68198
Agarwal, Pankaj K.; Kumar, Nirman; Sintos, Stavros; Suri, Subhash
2018
Unit interval vertex deletion: fewer vertices are relevant. Zbl 1391.68058
Ke, Yuping; Cao, Yixin; Ouyang, Xiating; Li, Wenjun; Wang, Jianxin
2018
On the complexity of two-dimensional signed majority cellular automata. Zbl 1378.68116
Goles, Eric; Montealegre, Pedro; Perrot, Kévin; Theyssier, Guillaume
2018
Optimal separation in exact query complexities for Simon’s problem. Zbl 1398.68173
Cai, Guangya; Qiu, Daowen
2018
What can be verified locally? Zbl 1398.68167
Balliu, Alkida; D&rsquo;Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis
2018
A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. Zbl 1402.68199
Eiben, Eduard; Ganian, Robert; Kwon, O-Joung
2018
Task-structured probabilistic I/O automata. Zbl 1390.68382
Canetti, Ran; Cheung, Ling; Kaynar, Dilsun; Liskov, Moses; Lynch, Nancy; Pereira, Olivier; Segala, Roberto
2018
Decomposition of quantum Markov chains and its applications. Zbl 1391.68079
Guan, Ji; Feng, Yuan; Ying, Mingsheng
2018
Homotopic properties of an MA-digitization of 2D Euclidean spaces. Zbl 1391.68110
Han, Sang-Eon
2018
Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs. Zbl 1380.68227
Kanj, Iyad; Komusiewicz, Christian; Sorge, Manuel; van Leeuwen, Erik Jan
2018
On the optimality of exact and approximation algorithms for scheduling problems. Zbl 1393.68056
Chen, Lin; Jansen, Klaus; Zhang, Guochuan
2018
Practically-self-stabilizing virtual synchrony. Zbl 1393.68029
Dolev, Shlomi; Georgiou, Chryssis; Marcoullis, Ioannis; Schiller, Elad M.
2018
The 2D dependency pair framework for conditional rewrite systems. I: Definition and basic processors. Zbl 1393.68088
Lucas, Salvador; Meseguer, José; Gutiérrez, Raúl
2018
Finding even subgraphs even faster. Zbl 1404.68050
Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket
2018
Strong bounds for evolution in networks. Zbl 1421.92025
Mertzios, George B.; Spirakis, Paul G.
2018
An improved algorithm for the minmax regret path centdian problem on trees. Zbl 1409.90214
Ye, Jhih-Hong; Li, Chih-Yu; Wang, Biing-Feng
2018
Adapting attackers and defenders patrolling strategies: a reinforcement learning approach for Stackelberg security games. Zbl 1394.91079
Trejo, Kristal K.; Clempner, Julio B.; Poznyak, Alexander S.
2018
Algorithmic identification of probabilities is hard. Zbl 1390.68360
Bienvenu, Laurent; Figueira, Santiago; Monin, Benoit; Shen, Alexander
2018
...and 1354 more Documents
all top 5

### Cited by 22,293 Authors

 111 Ibarra, Oscar H. 110 Saurabh, Saket 88 Jain, Sanjay 72 Niedermeier, Rolf 71 Fomin, Fedor V. 68 Kutrib, Martin 68 Stephan, Frank 63 Engelfriet, Joost 60 Fernau, Henning 59 Hemaspaandra, Lane A. 56 Rozenberg, Grzegorz 55 Goldreich, Oded 54 Otto, Friedrich 53 Golovach, Petr A. 53 Salomaa, Kai T. 52 Epstein, Leah 52 Lokshtanov, Daniel 52 Paschos, Vangelis Th. 52 Pelc, Andrzej 52 Raman, Venkatesh 50 Ésik, Zoltán 48 Vardi, Moshe Ya’akov 46 Gutin, Gregory Z. 46 Salomaa, Arto Kustaa 45 Courcelle, Bruno 45 Pilipczuk, Marcin L. 45 Rytter, Wojciech 44 Pilipczuk, Michał 43 Zehavi, Meirav 42 Cai, Jin-Yi 42 Chen, Jian-er 42 Holzer, Markus 41 Case, John 41 Demaine, Erik D. 41 Okhotin, Alexander 41 Pérez-Jiménez, Mario J. 40 Allender, Eric W. 40 Gottlob, Georg 40 Lohrey, Markus 40 Thilikos, Dimitrios M. 39 Alon, Noga M. 39 Szeider, Stefan 39 Wood, Derick 38 Malcher, Andreas 38 Rothe, Jörg-Matthias 37 Pan, Linqiang 37 Wigderson, Avi 36 Fellows, Michael Ralph 36 Papadimitriou, Christos Harilaos 36 Păun, Gheorghe 35 Bose, Prosenjit K. 35 Mauri, Giancarlo 34 Adámek, Jiří 34 Bodlaender, Hans L. 34 Crochemore, Maxime 34 Italiano, Giuseppe Francesco 34 Milius, Stefan 34 Paulusma, Daniël 34 Servedio, Rocco A. 34 Sharir, Micha 33 Marx, Dániel 33 Monnot, Jérôme 33 Spirakis, Paul G. 32 Chan, Timothy Moon-Yew 32 Cygan, Marek 32 Fortnow, Lance J. 32 Hromkovič, Juraj 32 Jansen, Bart M. P. 32 Köbler, Johannes 32 Kratsch, Stefan 32 Peleg, David 31 Book, Ronald Vernon 31 Eiter, Thomas 31 Heggernes, Pinar 31 Jiang, Tao 31 Karpinski, Marek 31 Sau, Ignasi 31 Woeginger, Gerhard Johannes 30 Chatterjee, Krishnendu 30 Guo, Jiong 30 Levin, Asaf 29 Arvind, Vikraman 29 Culik, Karel II 29 Komusiewicz, Christian 29 Lingas, Andrzej 29 Munro, J. Ian 29 Navarro, Gonzalo 29 Thérien, Denis 29 Wang, Jianxin 29 Watanabe, Osamu 29 Yeo, Anders 29 Yu, Sheng 28 Eppstein, David Arthur 28 Kanj, Iyad A. 28 Karhumaki, Juhani 28 Vogler, Heiko 28 Vollmer, Heribert 27 Bazgan, Cristina 27 Lutz, Jack H. 27 Pin, Jean-Eric ...and 22,193 more Authors
all top 5

### Cited in 758 Journals

 3,466 Theoretical Computer Science 1,545 Journal of Computer and System Sciences 1,048 Information Processing Letters 861 Algorithmica 769 Discrete Applied Mathematics 756 Information and Computation 398 Theory of Computing Systems 310 Information Sciences 307 International Journal of Foundations of Computer Science 272 Acta Informatica 235 Artificial Intelligence 227 SIAM Journal on Computing 223 Mathematical Systems Theory 190 Computational Geometry 186 European Journal of Operational Research 183 Journal of Combinatorial Optimization 180 Computational Complexity 148 Discrete Mathematics 147 Discrete & Computational Geometry 144 International Journal of Computer Mathematics 143 Annals of Pure and Applied Logic 141 Journal of Discrete Algorithms 137 Distributed Computing 130 Journal of Cryptology 130 Mathematical Programming. Series A. Series B 125 Machine Learning 120 Operations Research Letters 118 Annals of Mathematics and Artificial Intelligence 116 SIAM Journal on Discrete Mathematics 111 Journal of Symbolic Computation 97 International Journal of Approximate Reasoning 97 Logical Methods in Computer Science 91 RAIRO. Informatique Théorique et Applications 90 Combinatorica 90 RAIRO. Theoretical Informatics and Applications 85 Fuzzy Sets and Systems 82 Applied Mathematics and Computation 82 MSCS. Mathematical Structures in Computer Science 81 The Journal of Symbolic Logic 78 Journal of Complexity 76 RAIRO, Informatique Théorique 76 Computers & Operations Research 68 Computing 67 Pattern Recognition 65 International Journal of Computational Geometry & Applications 64 European Journal of Combinatorics 64 Formal Aspects of Computing 64 Annals of Operations Research 64 Discrete Optimization 63 Random Structures & Algorithms 61 Soft Computing 61 Natural Computing 60 Neural Computation 60 International Journal of Algebra and Computation 57 Journal of Mathematical Analysis and Applications 53 Journal of Automated Reasoning 53 Linear Algebra and its Applications 52 Computers & Mathematics with Applications 52 Quantum Information Processing 51 Networks 50 Journal of Scheduling 50 Journal of Logical and Algebraic Methods in Programming 49 Journal of Combinatorial Theory. Series B 48 Journal of Machine Learning Research (JMLR) 47 The Annals of Statistics 47 BIT 47 Journal of Optimization Theory and Applications 47 Theory and Practice of Logic Programming 46 Formal Methods in System Design 45 International Journal of Theoretical Physics 45 Mathematics of Computation 45 Automatica 45 Designs, Codes and Cryptography 45 ACM Transactions on Computational Logic 44 Computer Science Review 42 Combinatorics, Probability and Computing 40 Cybernetics 40 The Journal of Logic and Algebraic Programming 39 International Journal of Computer & Information Sciences 39 New Generation Computing 39 Journal of Membrane Computing 38 Journal of Computer Science and Technology 38 Journal of Applied Logic 37 Journal of Applied Non-Classical Logics 37 Algorithms 36 Cybernetics and Systems Analysis 35 Studia Logica 35 Journal of Intelligent and Fuzzy Systems 34 Mathematics of Operations Research 33 Journal of Algebra 33 Computational Statistics and Data Analysis 33 Journal of Logic, Language and Information 32 Semigroup Forum 32 Physica D 32 Mathematical Problems in Engineering 31 Journal of Soviet Mathematics 31 Journal of Global Optimization 31 Discrete Event Dynamic Systems 31 The Electronic Journal of Combinatorics 30 Journal of Combinatorial Theory. Series A ...and 658 more Journals
all top 5

### Cited in 62 Fields

 17,376 Computer science (68-XX) 3,746 Combinatorics (05-XX) 2,598 Operations research, mathematical programming (90-XX) 2,487 Mathematical logic and foundations (03-XX) 1,417 Information and communication theory, circuits (94-XX) 1,103 Game theory, economics, finance, and other social and behavioral sciences (91-XX) 742 Numerical analysis (65-XX) 684 Statistics (62-XX) 461 Biology and other natural sciences (92-XX) 435 Probability theory and stochastic processes (60-XX) 426 Group theory and generalizations (20-XX) 391 Quantum theory (81-XX) 358 Number theory (11-XX) 334 Systems theory; control (93-XX) 291 Convex and discrete geometry (52-XX) 287 Order, lattices, ordered algebraic structures (06-XX) 245 Linear and multilinear algebra; matrix theory (15-XX) 234 Dynamical systems and ergodic theory (37-XX) 211 Category theory; homological algebra (18-XX) 174 General algebraic systems (08-XX) 113 Calculus of variations and optimal control; optimization (49-XX) 108 Ordinary differential equations (34-XX) 98 Statistical mechanics, structure of matter (82-XX) 96 Field theory and polynomials (12-XX) 88 General topology (54-XX) 76 Algebraic geometry (14-XX) 76 Functional analysis (46-XX) 75 Commutative algebra (13-XX) 69 Approximations and expansions (41-XX) 66 Operator theory (47-XX) 65 Measure and integration (28-XX) 63 Associative rings and algebras (16-XX) 53 Geometry (51-XX) 50 History and biography (01-XX) 46 Partial differential equations (35-XX) 42 General and overarching topics; collections (00-XX) 33 Real functions (26-XX) 31 Harmonic analysis on Euclidean spaces (42-XX) 29 Manifolds and cell complexes (57-XX) 24 Functions of a complex variable (30-XX) 24 Integral equations (45-XX) 23 Algebraic topology (55-XX) 19 Fluid mechanics (76-XX) 18 Global analysis, analysis on manifolds (58-XX) 17 Differential geometry (53-XX) 15 Difference and functional equations (39-XX) 15 Mechanics of deformable solids (74-XX) 14 Mechanics of particles and systems (70-XX) 13 Topological groups, Lie groups (22-XX) 7 Sequences, series, summability (40-XX) 7 Abstract harmonic analysis (43-XX) 7 Integral transforms, operational calculus (44-XX) 7 Geophysics (86-XX) 5 Special functions (33-XX) 5 Optics, electromagnetic theory (78-XX) 3 Nonassociative rings and algebras (17-XX) 3 Relativity and gravitational theory (83-XX) 2 Potential theory (31-XX) 2 Several complex variables and analytic spaces (32-XX) 2 Astronomy and astrophysics (85-XX) 2 Mathematics education (97-XX) 1 Classical thermodynamics, heat transfer (80-XX)