×

zbMATH — the first resource for mathematics

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: 2,997 Publications (since 1967)
References Indexed: 2,724 Publications with 66,830 References.
all top 5

Latest Issues

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)
75, No. 4 (2009)
75, No. 3 (2009)
75, No. 2 (2009)
75, No. 1 (2009)
74, No. 8 (2008)
74, No. 7 (2008)
...and 174 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 Vardi, Moshe Y.
11 Case, John
11 Hemaspaandra, Lane A.
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 Sagiv, Yehoshua
9 Van den Bussche, Jan
8 Buhrman, Harry
8 Epstein, Leah
8 Fagin, Ronald
8 Gyssens, Marc
8 Harel, David
8 Hartmanis, Juris
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 Hsieh, Sun-Yuan
7 Immerman, Neil
7 Jerrum, Mark R.
7 Jiang, Tao
7 Kanj, Iyad A.
7 Kleinberg, Jon Michael
7 Köbler, Johannes
7 Ladner, Richard E.
7 Ma, Bin
7 Paredaens, Jan
7 Paulusma, Daniël
7 Pnueli, Amir
7 Raghavan, Prabhakar
7 Selman, Alan L.
7 Spanier, Edwin Henry
7 Spirakis, Paul G.
7 Srinivasan, Aravind
7 Takizawa, Makoto
7 Taniar, David
7 Tarjan, Robert Endre
7 Wang, Lusheng
6 Afrati, Foto N.
6 Agrawal, Manindra
6 Bartlett, Peter L.
...and 3,886 more Authors
all top 5

Fields

2,726 Computer science (68-XX)
307 Mathematical logic and foundations (03-XX)
239 Combinatorics (05-XX)
145 Information and communication theory, circuits (94-XX)
132 Operations research, mathematical programming (90-XX)
86 General and overarching topics; collections (00-XX)
67 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
59 Biology and other natural sciences (92-XX)
57 Numerical analysis (65-XX)
40 Group theory and generalizations (20-XX)
29 Number theory (11-XX)
29 Category theory; homological algebra (18-XX)
24 Probability theory and stochastic processes (60-XX)
24 Statistics (62-XX)
23 Quantum theory (81-XX)
23 Systems theory; control (93-XX)
20 Order, lattices, ordered algebraic structures (06-XX)
19 Linear and multilinear algebra; matrix theory (15-XX)
16 Dynamical systems and ergodic theory (37-XX)
14 General algebraic systems (08-XX)
12 Convex and discrete geometry (52-XX)
7 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 Geometry (51-XX)
4 Statistical mechanics, structure of matter (82-XX)
3 Algebraic geometry (14-XX)
3 Ordinary differential equations (34-XX)
3 Operator theory (47-XX)
2 Topological groups, Lie groups (22-XX)
2 Partial differential equations (35-XX)
2 Harmonic analysis on Euclidean spaces (42-XX)
2 Algebraic topology (55-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

Citations contained in zbMATH Open

2,328 Publications have been cited 32,280 times in 21,792 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.
408
1976
Optimization, approximation, and complexity classes. Zbl 0765.68036
Papadimitriou, Christos H.; Yannakakis, Mihalis
389
1991
A decision-theoretic generalization of on-line learning and an application to boosting. Zbl 0880.68103
Freund, Yoav; Schapire, Robert E.
375
1997
Approximation algorithms for combinatorial problems. Zbl 0296.65036
Johnson, David S.
336
1974
Which problems have strongly exponential complexity? Zbl 1006.68052
Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
331
2001
Relationships between nondeterministic and deterministic tape complexities. Zbl 0188.33502
Savitch, W. J.
327
1970
Computing with membranes. Zbl 0956.68055
Păun, Gheorghe
290
2000
Probabilistic encryption. Zbl 0563.94013
Goldwasser, Shafi; Micali, Silvio
251
1984
On the computational power of pushdown automata. Zbl 0207.01701
Aho, A. V.; Ullman, J. D.; Hopcroft, J. E.
245
1970
On the complexity of \(k\)-SAT. Zbl 0990.68079
Impagliazzo, Russell; Paturi, Ramamohan
211
2001
Propositional dynamic logic of regular programs. Zbl 0408.03014
Fischer, Michael J.; Ladner, Richard E.
211
1979
Time bounds for selection. Zbl 0278.68033
Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E.
208
1973
Universal classes of hash functions. Zbl 0412.68090
Carter, J. Lawrence; Wegman, Mark N.
200
1979
Variable precision rough set model. Zbl 0764.68162
Ziarko, Wojciech
196
1993
A theory of type polymorphism in programming. Zbl 0388.68003
Milner, Robin
183
1978
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
173
2009
A data structure for dynamic trees. Zbl 0509.68058
Sleator, Daniel D.; Tarjan, Robert Endre
170
1983
Parallel program schemata. Zbl 0198.32603
Karp, Richard M.; Miller, Raymond E.
167
1969
Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). Zbl 0667.68059
Barrington, David A.
159
1989
The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029
Lewis, John M.; Yannakakis, Mihalis
153
1980
Optimization of LR(k) parsers. Zbl 0264.68032
Aho, A. V.; Ullman, J. D.
153
1972
Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061
Khot, Subhash; Regev, Oded
147
2008
Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074
Yannakakis, Mihalis
139
1991
Hardness vs randomness. Zbl 0821.68057
Nisan, Noam; Wigderson, Avi
139
1994
Fast probabilistic algorithms for Hamiltonian circuits and matchings. Zbl 0437.05040
Angluin, D.; Valiant, L. G.
137
1979
Self-testing/correcting with applications to numerical problems. Zbl 0795.68131
Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt
136
1993
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
131
1988
Handle-rewriting hypergraph grammars. Zbl 0825.68446
Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz
130
1993
On uniform circuit complexity. Zbl 0462.68013
Ruzzo, Walter L.
127
1981
Isomorphism of graphs of bounded valence can be tested in polynomial time. Zbl 0493.68064
Luks, Eugene M.
126
1982
Finding patterns common to a set of strings. Zbl 0454.68108
Angluin, Dana
125
1980
A linear-time algorithm for a special case of disjoint set union. Zbl 0572.68058
Gabow, Harold N.; Tarjan, Robert Endre
123
1985
On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048
Papadimitriou, Christos H.
120
1994
Tree acceptors and some of their applications. Zbl 0212.02901
Doner, John
114
1970
The complexity of optimization problems. Zbl 0652.68040
Krentel, Mark W.
106
1988
NP-complete scheduling problems. Zbl 0313.68054
Ullman, J. D.
106
1975
Fast algorithms for bin packing. Zbl 0284.68023
Johnson, David S.
105
1974
A faster algorithm computing string edit distances. Zbl 0436.68044
Masek, William J.; Paterson, Michael S.
104
1980
New hash functions and their use in authentication and set equality. Zbl 0461.68074
Wegman, Mark N.; Carter, J. Lawrence
104
1981
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
104
1990
Structure and complexity of relational queries. Zbl 0511.68073
Chandra, Ashok; Harel, David
102
1982
Reversal-bounded multipushdown machines. Zbl 0309.68043
Baker, Brenda S.; Book, Ronald V.
101
1974
Maintenance of configurations in the plane. Zbl 0474.68082
Overmars, Mark H.; van Leeuwen, Jan
100
1981
What’s decidable about hybrid automata? Zbl 0920.68091
Henzinger, Thomas A.; Kopke, Peter W.; Puri, Anuj; Varaiya, Pravin
99
1998
Space-bounded reducibility among combinatorial problems. Zbl 0317.02039
Jones, Neil D.
98
1975
The space complexity of approximating the frequency moments. Zbl 0938.68153
Alon, Noga; Matias, Yossi; Szegedy, Mario
97
1999
Relaxing the uniformity and independence assumptions using the concept of fractal dimension. Zbl 0889.68050
Faloutsos, Christos; Kamel, Ibrahim
95
1997
Riemann’s hypothesis and tests for primality. Zbl 0349.68025
Miller, Gary L.
95
1976
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029
Babai, László; Moran, Shlomo
94
1988
The complexity of facets (and some facets of complexity). Zbl 0571.68028
Papadimitriou, C. H.; Yannakakis, M.
92
1984
A framework for solving VLSI graph layout problems. Zbl 0543.68052
Bhatt, Sandeep N.; Leighton, Frank Thompson
89
1984
Marked directed graphs. Zbl 0238.05109
Commoner, F.; Holt, A. W.; Even, S.; Pnueli, A.
89
1971
Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Zbl 0263.94019
Amoroso, S.; Patt, Y. N.
89
1972
Classifying regular events in symbolic logic. Zbl 0503.68055
Thomas, Wolfgang
88
1982
Process complexity and effective random tests. Zbl 0273.68036
Schnorr, C. P.
87
1973
Groups, the theory of ends, and context-free languages. Zbl 0537.20011
Muller, David E.; Schupp, Paul E.
85
1983
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040
Achlioptas, Dimitris
84
2003
Probabilistic construction of deterministic algorithms: approximating packing integer programs. Zbl 0659.90066
Raghavan, Prabhakar
83
1988
Making data structures persistent. Zbl 0667.68026
Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E.
82
1989
Generalized sequential machine maps. Zbl 0198.03303
Thatcher, J. W.
82
1970
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Zbl 0493.68043
Mahaney, Stephen R.
81
1982
Computable queries for relational data bases. Zbl 0456.68128
Chandra, Ashok K.; Harel, David
80
1980
Topologically sweeping an arrangement. Zbl 0676.68013
Edelsbrunner, Herbert; Guibas, Leonidas J.
79
1989
In search of an easy witness: Exponential time vs. probabilistic polynomial time. Zbl 1059.68047
Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi
79
2002
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
79
1992
Multiattribute decision making models and methods using intuitionistic fuzzy sets. Zbl 1066.90052
Li, Deng-Feng
79
2005
A complete inference system for a class of regular behaviours. Zbl 0562.68065
Milner, Robin
78
1984
On the complexity of teaching. Zbl 0939.68770
Goldman, Sally A.; Kearns, Michael J.
78
1995
Almost everywhere high nonuniform complexity. Zbl 0767.68043
Lutz, Jack H.
78
1992
A tight bound on approximating arbitrary metrics by tree metrics. Zbl 1071.68082
Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal
76
2004
Adherences of languages. Zbl 0471.68052
Boasson, Luc; Nivat, Maurice
76
1980
Tesselations with local transformations. Zbl 0246.94037
Richardson, D.
76
1972
Zero knowledge and the chromatic number. Zbl 0921.68089
Feige, Uriel; Kilian, Joe
75
1998
Decision procedures and expressiveness in the temporal logic of branching time. Zbl 0559.68051
Emerson, E. Allen; Halpern, Joseph Y.
74
1985
Randomness is linear in space. Zbl 0846.68041
Nisan, Noam; Zuckerman, David
74
1996
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
74
2011
On the complexity of some two-person perfect-information games. Zbl 0383.90112
Schaefer, Thomas J.
74
1978
Linear unification. Zbl 0371.68013
Paterson, M. S.; Wegman, M. N.
73
1978
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045
Gabber, Ofer; Galil, Zvi
72
1981
An information statistics approach to data stream and communication complexity. Zbl 1074.68022
Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
71
2004
Automata-theoretic techniques for modal logics of programs. Zbl 0622.03017
Vardi, Moshe Y.; Wolper, Pierre
70
1986
Tree-size bounded alternation. Zbl 0445.68034
Ruzzo, Walter L.
69
1980
The average height of binary trees and other simple trees. Zbl 0499.68027
Flajolet, Philippe; Odlyzko, Andrew
69
1982
Minimum disclosure proofs of knowledge. Zbl 0656.68109
Brassard, Gilles; Chaum, David; Crépeau, Claude
68
1988
Surpassing the information theoretic bound with fusion trees. Zbl 0795.68049
Fredman, Michael L.; Willard, Dan E.
68
1993
Conjunctive-query containment and constraint satisfaction. Zbl 0963.68059
Kolaitis, Phokion G.; Vardi, Moshe Y.
68
2000
Power domains. Zbl 0391.68011
Smyth, M. B.
68
1978
Natural proofs. Zbl 0884.68055
Razborov, Alexander A.; Rudich, Steven
66
1997
Solving reflexive domain equations in a category of complete metric spaces. Zbl 0717.18002
America, Pierre; Rutten, Jan
66
1989
Teaching a smarter learner. Zbl 1152.68451
Goldman, Sally A.; Mathias, H. David
64
1996
Varieties of ordered algebras. Zbl 0337.06008
Bloom, Stephen L.
64
1976
Structure preserving reductions among convex optimization problems. Zbl 0441.68049
Ausiello, G.; D’Atri, A.; Protasi, M.
63
1980
Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Zbl 0155.01802
Thatcher, J. W.
63
1967
Probabilistic counting algorithms for data base applications. Zbl 0583.68059
Flajolet, Philippe; Martin, G. Nigel
61
1985
Real-time language recognition by one-dimensional cellular automata. Zbl 0268.68044
Smith, Alvy Ray III
61
1972
Time bounded random access machines. Zbl 0284.68038
Cook, Stephen A.; Reckhow, Robert A.
61
1973
The dot-depth hierarchy of star-free languages is infinite. Zbl 0368.68074
Brzozowski, J. A.; Knast, R.
61
1978
Faster shortest-path algorithms for planar graphs. Zbl 0880.68099
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam
60
1997
Reversibility and surjectivity problems of cellular automata. Zbl 0802.68090
Kari, Jarkko
60
1994
Optimal shortest path queries in a simple polygon. Zbl 0681.68065
Guibas, Leonidas J.; Hershberger, John
58
1989
Assigning times to minimise reachability in temporal graphs. Zbl 1464.68283
Enright, Jessica; Meeks, Kitty; Skerman, Fiona
1
2021
Deleting edges to restrict the size of an epidemic in temporal networks. Zbl 07332991
Enright, Jessica; Meeks, Kitty; Mertzios, George B.; Zamaraev, Viktor
1
2021
When are emptiness and containment decidable for probabilistic automata? Zbl 07332992
Daviaud, Laure; Jurdziński, Marcin; Lazić, Ranko; Mazowiecki, Filip; Pérez, Guillermo A.; Worrell, James
1
2021
Bisection of bounded treewidth graphs by convolutions. Zbl 07332994
Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E.
1
2021
Block trees. Zbl 07304637
Belazzougui, Djamal; Cáceres, Manuel; Gagie, Travis; Gawrychowski, Paweł; Kärkkäinen, Juha; Navarro, Gonzalo; Ordóñez, Alberto; Puglisi, Simon J.; Tabei, Yasuo
1
2021
On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Zbl 07304639
Caragiannis, Ioannis; Fanelli, Angelo
1
2021
Temporal cliques admit sparse spanners. Zbl 07368158
Casteigts, Arnaud; Peters, Joseph G.; Schoeters, Jason
1
2021
2-D Tucker is PPA complete. Zbl 1436.68127
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
5
2020
Graphs are not universal for online computability. Zbl 07210414
Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel
5
2020
The complexity of finding small separators in temporal graphs. Zbl 1436.68265
Zschoche, Philipp; Fluschnik, Till; Molter, Hendrik; Niedermeier, Rolf
4
2020
Temporal vertex cover with a sliding time window. Zbl 1436.68219
Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Zamaraev, Viktor
4
2020
Unique end of potential line. Zbl 1461.68086
Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul
4
2020
Vulnerability of super extra edge-connected graphs. Zbl 1436.68225
Cheng, Chia-Wen; Hsieh, Sun-Yuan; Klasing, Ralf
3
2020
Clique-width and well-quasi-ordering of triangle-free graph classes. Zbl 1442.05184
Dabrowski, Konrad K.; Lozin, Vadim V.; Paulusma, Daniël
2
2020
Eccentricity terrain of \(\delta\)-hyperbolic graphs. Zbl 1450.05017
Dragan, Feodor F.; Guarnera, Heather M.
2
2020
Deciding probabilistic bisimilarity distance one for probabilistic automata. Zbl 1432.68247
Tang, Qiyi; van Breugel, Franck
2
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
2
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
1
2020
On the degrees of non-regularity and non-context-freeness. Zbl 1447.68006
Bordihn, Henning; Mitrana, Victor
1
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
1
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
1
2020
On Weisfeiler-Leman invariance: subgraph counts and related graph properties. Zbl 1450.05056
Arvind, V.; Fuhlbrück, Frank; Köbler, Johannes; Verbitsky, Oleg
1
2020
Disconnected cuts in claw-free graphs. Zbl 1450.05073
Martin, Barnaby; Paulusma, Daniël; van Leeuwen, Erik Jan
1
2020
A counterexample to Thiagarajan’s conjecture on regular event structures. Zbl 1442.68131
Chalopin, Jérémie; Chepoi, Victor
1
2020
Deciding semantic finiteness of pushdown processes and first-order grammars w.r.t. bisimulation equivalence. Zbl 1435.68169
Jančar, Petr
1
2020
Hitting minors on bounded treewidth graphs. III. Lower bounds. Zbl 1435.68121
Baste, Julien; Sau, Ignasi; Thilikos, Dimitrios M.
1
2020
Subexponential algorithms for variants of the homomorphism problem in string graphs. Zbl 1435.68243
Okrasa, Karolina; Rzążewski, Paweł
1
2020
The complexity of synthesizing elementary net systems relative to natural parameters. Zbl 1435.68214
Rosenke, Christian; Tredup, Ronny
1
2020
Subquadratic non-adaptive threshold group testing. Zbl 1432.68177
De Marco, Gianluca; Jurdziński, Tomasz; Kowalski, Dariusz R.; Różański, Michał; Stachowiak, Grzegorz
1
2020
Counting and enumerating tree-child networks and their subclasses. Zbl 1448.92147
Cardona, Gabriel; Zhang, Louxin
1
2020
On the transformation capability of feasible mechanisms for programmable matter. Zbl 1421.68158
Michail, Othon; Skretas, George; Spirakis, Paul G.
4
2019
Temporal flows in temporal networks. Zbl 1423.68324
Akrida, Eleni C.; Czyzowicz, Jurek; Gąsieniec, Leszek; Kuszner, Łukasz; Spirakis, Paul G.
4
2019
Bounding clique-width via perfect graphs. Zbl 1428.05220
Dabrowski, Konrad K.; Huang, Shenwei; Paulusma, Daniël
3
2019
Colouring square-free graphs without long induced paths. Zbl 1429.68081
Gaspers, Serge; Huang, Shenwei; Paulusma, Daniël
2
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.
2
2019
Parameterized aspects of triangle enumeration. Zbl 1430.68176
Bentert, Matthias; Fluschnik, Till; Nichterlein, André; Niedermeier, Rolf
2
2019
Hide and seek with repetitions. Zbl 1410.68309
Gawrychowski, Paweł; Manea, Florin; Mercaş, Robert; Nowotka, Dirk
2
2019
Copyless cost-register automata: structure, expressiveness, and closure properties. Zbl 1421.68050
Mazowiecki, Filip; Riveros, Cristian
1
2019
The complexity of routing with collision avoidance. Zbl 1421.68076
Fluschnik, Till; Morik, Marco; Sorge, Manuel
1
2019
Deterministic rendezvous with different maps. Zbl 1439.68029
Farrugia, Ashley; Gąsieniec, Leszek; Kuszner, Łukasz; Pacheco, Eduardo
1
2019
Does adding more agents make a difference? A case study of cover time for the rotor-router. Zbl 1429.68311
Kosowski, Adrian; Pająk, Dominik
1
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.
1
2019
Calculi for symmetric queries. Zbl 1423.68139
Gyssens, Marc; Hellings, Jelle; Paredaens, Jan; Van Gucht, Dirk; Wijsen, Jef; Wu, Yuqing
1
2019
Fault-tolerant embedding of starlike trees into restricted hypercube-like graphs. Zbl 1423.68355
Park, Jung-Heum; Lim, Hyeong-Seok; Kim, Hee-Chul
1
2019
On notions of distortion and an almost minimum spanning tree with constant average distortion. Zbl 1423.68326
Bartal, Yair; Filtser, Arnold; Neiman, Ofer
1
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
1
2019
Finite-state independence and normal sequences. Zbl 1423.68239
Álvarez, Nicolás; Becher, Verónica; Carton, Olivier
1
2019
A game characterisation of tree-like Q-resolution size. Zbl 1425.03028
Beyersdorff, Olaf; Chew, Leroy; Sreenivasaiah, Karteek
1
2019
Insertion operations on deterministic reversal-bounded counter machines. Zbl 1423.68250
Eremondi, Joey; Ibarra, Oscar H.; McQuillan, Ian
1
2019
Classifying invariant structures of step traces. Zbl 1423.68310
Janicki, Ryszard; Kleijn, Jetty; Koutny, Maciej; Mikulski, Łukasz
1
2019
Path-contractions, edge deletions and connectivity preservation. Zbl 1412.68084
Gutin, Gregory; Ramanujan, M. S.; Reidl, Felix; Wahlström, Magnus
1
2019
Recursion-theoretic ranking and compression. Zbl 1459.03059
Hemaspaandra, Lane A.; Rubery, Daniel
1
2019
Computational capabilities of analog and evolving neural networks over infinite input streams. Zbl 1410.68120
Cabessa, Jérémie; Finkel, Olivier
1
2019
Reconfiguration in bounded bandwidth and tree-depth. Zbl 1382.68183
Wrochna, Marcin
18
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
8
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
7
2018
SOS specifications for uniformly continuous operators. Zbl 1380.68296
Gebler, Daniel; Tini, Simone
7
2018
On discrete preferences and coordination. Zbl 1408.91041
Chierichetti, Flavio; Kleinberg, Jon; Oren, Sigal
6
2018
Towards a unified complexity theory of total functions. Zbl 1393.68053
Goldberg, Paul W.; Papadimitriou, Christos H.
6
2018
On the complexity of two-dimensional signed majority cellular automata. Zbl 1378.68116
Goles, Eric; Montealegre, Pedro; Perrot, Kévin; Theyssier, Guillaume
4
2018
Unit interval vertex deletion: fewer vertices are relevant. Zbl 1391.68058
Ke, Yuping; Cao, Yixin; Ouyang, Xiating; Li, Wenjun; Wang, Jianxin
4
2018
Reconfiguration on sparse graphs. Zbl 1390.68351
Lokshtanov, Daniel; Mouawad, Amer E.; Panolan, Fahad; Ramanujan, M. S.; Saurabh, Saket
4
2018
A single-exponential fixed-parameter algorithm for distance-hereditary vertex deletion. Zbl 1402.68199
Eiben, Eduard; Ganian, Robert; Kwon, O-Joung
3
2018
Parameterized algorithms for recognizing monopolar and 2-subcolorable graphs. Zbl 1380.68227
Kanj, Iyad; Komusiewicz, Christian; Sorge, Manuel; van Leeuwen, Erik Jan
3
2018
Task-structured probabilistic I/O automata. Zbl 1390.68382
Canetti, Ran; Cheung, Ling; Kaynar, Dilsun; Liskov, Moses; Lynch, Nancy; Pereira, Olivier; Segala, Roberto
3
2018
Finding even subgraphs even faster. Zbl 1404.68050
Goyal, Prachi; Misra, Pranabendu; Panolan, Fahad; Philip, Geevarghese; Saurabh, Saket
2
2018
Optimal separation in exact query complexities for Simon’s problem. Zbl 1398.68173
Cai, Guangya; Qiu, Daowen
2
2018
What can be verified locally? Zbl 1398.68167
Balliu, Alkida; D’Angelo, Gianlorenzo; Fraigniaud, Pierre; Olivetti, Dennis
2
2018
Trace malicious source to guarantee cyber security for mass monitor critical infrastructure. Zbl 1400.68039
Liu, Xiao; Dong, Mianxiong; Ota, Kaoru; Yang, Laurence T.; Liu, Anfeng
2
2018
Kernels for deletion to classes of acyclic digraphs. Zbl 1380.68207
Agrawal, Akanksha; Saurabh, Saket; Sharma, Roohani; Zehavi, Meirav
2
2018
Approximability and inapproximability of the star \(p\)-hub center problem with parameterized triangle inequality. Zbl 1380.68309
Chen, Li-Hsuan; Cheng, Dun-Wei; Hsieh, Sun-Yuan; Hung, Ling-Ju; Klasing, Ralf; Lee, Chia-Wei; Wu, Bang Ye
2
2018
On the optimality of exact and approximation algorithms for scheduling problems. Zbl 1393.68056
Chen, Lin; Jansen, Klaus; Zhang, Guochuan
2
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
2
2018
Pebbling meets coloring: reversible pebble game on trees. Zbl 1378.68085
Komarath, Balagopal; Sarma, Jayalal; Sawlani, Saurabh
2
2018
Decomposition of quantum Markov chains and its applications. Zbl 1391.68079
Guan, Ji; Feng, Yuan; Ying, Mingsheng
2
2018
Algorithmic identification of probabilities is hard. Zbl 1390.68360
Bienvenu, Laurent; Figueira, Santiago; Monin, Benoit; Shen, Alexander
2
2018
Homotopic properties of an MA-digitization of 2D Euclidean spaces. Zbl 1391.68110
Han, Sang-Eon
2
2018
Simple picture processing based on finite automata and regular grammars. Zbl 1390.68393
Fernau, Henning; Paramasivan, Meenakshi; Schmid, Markus L.; Thomas, D. Gnanaraj
2
2018
Range-max queries on uncertain data. Zbl 1390.68198
Agarwal, Pankaj K.; Kumar, Nirman; Sintos, Stavros; Suri, Subhash
2
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
1
2018
Visibly pushdown transducers. Zbl 1398.68307
Filiot, Emmanuel; Raskin, Jean-François; Reynier, Pierre-Alain; Servais, Frédéric; Talbot, Jean-Marc
1
2018
Abstract geometrical computation. VIII: Small machines, accumulations & rationality. Zbl 1398.68158
Becker, Florent; Chapelle, Mathieu; Durand-Lose, Jérôme; Levorato, Vincent; Senot, Maxime
1
2018
Containment of queries for graphs with data. Zbl 1380.68168
Kostylev, Egor V.; Reutter, Juan L.; Vrgoč, Domagoj
1
2018
Practically-self-stabilizing virtual synchrony. Zbl 1393.68029
Dolev, Shlomi; Georgiou, Chryssis; Marcoullis, Ioannis; Schiller, Elad M.
1
2018
A generic framework for checking semantic equivalences between pushdown automata and finite-state automata. Zbl 1378.68106
Kučera, Antonín; Mayr, Richard
1
2018
Dual power assignment via second Hamiltonian cycle. Zbl 1383.68062
Karim Abu-Affash, A.; Carmi, Paz; Parush Tzur, Anat
1
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.
1
2018
\(k\)-distinct in- and out-branchings in digraphs. Zbl 1391.68054
Gutin, Gregory; Reidl, Felix; Wahlström, Magnus
1
2018
Topological analysis of voxelized objects by discrete geodesic Reeb graph. Zbl 1390.68708
Bhunre, Piyush Kanti; Bhowmick, Partha
1
2018
Dominant point detection based on discrete curve structure and applications. Zbl 1391.68114
Nasser, Hayat; Ngo, Phuc; Debled-Rennesson, Isabelle
1
2018
Object digitization up to a translation. Zbl 1390.68724
Mazo, Loïc; Baudrier, Étienne
1
2018
Optimal consensus set for digital flake hyperspheres in \(n\)D. Zbl 1391.68118
Zrour, Rita; Largeteau-Skapin, Gaelle; Andres, Eric
1
2018
Computing marginals using MapReduce. Zbl 1390.68194
Afrati, Foto N.; Sharma, Shantanu; Ullman, Jonathan R.; Ullman, Jeffrey D.
1
2018
Narrow sieves for parameterized paths and packings. Zbl 1370.68321
Björklund, Andreas; Husfeldt, Thore; Kaski, Petteri; Koivisto, Mikko
44
2017
Kernelization using structural parameters on sparse graph classes. Zbl 1353.68127
Gajarský, Jakub; Hliněný, Petr; Obdržálek, Jan; Ordyniak, Sebastian; Reidl, Felix; Rossmanith, Peter; Sánchez Villaamil, Fernando; Sikdar, Somnath
17
2017
On \(g\)-extra connectivity of hypercube-like networks. Zbl 1371.68218
Zhou, Jin-Xin
12
2017
Colouring diamond-free graphs. Zbl 1372.05067
Dabrowski, Konrad K.; Dross, François; Paulusma, Daniël
9
2017
Decidability of order-based modal logics. Zbl 1423.03056
Caicedo, Xavier; Metcalfe, George; Rodríguez, Ricardo; Rogger, Jonas
8
2017
On the advice complexity of the \(k\)-server problem. Zbl 1370.68333
Böckenhauer, Hans-Joachim; Komm, Dennis; Královič, Rastislav; Královič, Richard
7
2017
On a generalization of Nemhauser and Trotter’s local optimization theorem. Zbl 1353.68138
Xiao, Mingyu
7
2017
...and 1350 more Documents
all top 5

Cited by 20,950 Authors

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

Cited in 723 Journals

3,392 Theoretical Computer Science
1,514 Journal of Computer and System Sciences
1,035 Information Processing Letters
820 Algorithmica
755 Discrete Applied Mathematics
722 Information and Computation
385 Theory of Computing Systems
307 International Journal of Foundations of Computer Science
295 Information Sciences
267 Acta Informatica
223 Mathematical Systems Theory
211 Artificial Intelligence
208 SIAM Journal on Computing
186 Computational Geometry
181 European Journal of Operational Research
177 Journal of Combinatorial Optimization
176 Computational Complexity
145 Discrete Mathematics
144 International Journal of Computer Mathematics
143 Annals of Pure and Applied Logic
143 Discrete & Computational Geometry
141 Journal of Discrete Algorithms
126 Distributed Computing
125 Journal of Cryptology
124 Mathematical Programming. Series A. Series B
115 Operations Research Letters
115 Annals of Mathematics and Artificial Intelligence
110 Journal of Symbolic Computation
100 SIAM Journal on Discrete Mathematics
91 RAIRO. Informatique Théorique et Applications
90 RAIRO. Theoretical Informatics and Applications
86 International Journal of Approximate Reasoning
85 Fuzzy Sets and Systems
85 Combinatorica
80 Applied Mathematics and Computation
80 The Journal of Symbolic Logic
79 Logical Methods in Computer Science
78 Machine Learning
78 MSCS. Mathematical Structures in Computer Science
77 Journal of Complexity
76 RAIRO, Informatique Théorique
72 Computers & Operations Research
67 Pattern Recognition
66 Computing
65 International Journal of Computational Geometry & Applications
64 Formal Aspects of Computing
63 Random Structures & Algorithms
62 Discrete Optimization
61 European Journal of Combinatorics
61 Soft Computing
61 Natural Computing
60 Annals of Operations Research
59 International Journal of Algebra and Computation
58 Neural Computation
57 Journal of Mathematical Analysis and Applications
53 Linear Algebra and its Applications
52 Computers & Mathematics with Applications
52 Journal of Automated Reasoning
52 Quantum Information Processing
51 Networks
48 Journal of Combinatorial Theory. Series B
47 BIT
47 Journal of Optimization Theory and Applications
47 Journal of Scheduling
47 Theory and Practice of Logic Programming
47 Journal of Logical and Algebraic Methods in Programming
45 Mathematics of Computation
45 Formal Methods in System Design
45 ACM Transactions on Computational Logic
43 The Annals of Statistics
42 Automatica
42 Designs, Codes and Cryptography
42 Combinatorics, Probability and Computing
42 Journal of Machine Learning Research (JMLR)
40 Cybernetics
40 The Journal of Logic and Algebraic Programming
39 International Journal of Computer & Information Sciences
39 New Generation Computing
39 Computer Science Review
39 Journal of Membrane Computing
38 Journal of Computer Science and Technology
38 Journal of Applied Logic
37 Algorithms
36 International Journal of Theoretical Physics
36 Cybernetics and Systems Analysis
36 Journal of Applied Non-Classical Logics
35 Studia Logica
35 Journal of Intelligent and Fuzzy Systems
33 Journal of Algebra
33 Journal of Logic, Language and Information
32 Semigroup Forum
32 Computational Statistics and Data Analysis
32 Mathematical Problems in Engineering
31 Journal of Soviet Mathematics
30 Transactions of the American Mathematical Society
29 Kybernetika
29 Physica D
29 Real-Time Systems
29 Journal of Global Optimization
29 Journal of Functional Programming
...and 623 more Journals
all top 5

Cited in 61 Fields

16,491 Computer science (68-XX)
3,513 Combinatorics (05-XX)
2,486 Operations research, mathematical programming (90-XX)
2,376 Mathematical logic and foundations (03-XX)
1,290 Information and communication theory, circuits (94-XX)
1,015 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
711 Numerical analysis (65-XX)
592 Statistics (62-XX)
438 Biology and other natural sciences (92-XX)
415 Group theory and generalizations (20-XX)
406 Probability theory and stochastic processes (60-XX)
364 Quantum theory (81-XX)
335 Number theory (11-XX)
316 Systems theory; control (93-XX)
275 Convex and discrete geometry (52-XX)
273 Order, lattices, ordered algebraic structures (06-XX)
233 Linear and multilinear algebra; matrix theory (15-XX)
223 Dynamical systems and ergodic theory (37-XX)
198 Category theory; homological algebra (18-XX)
158 General algebraic systems (08-XX)
109 Calculus of variations and optimal control; optimization (49-XX)
105 Ordinary differential equations (34-XX)
95 Field theory and polynomials (12-XX)
90 Statistical mechanics, structure of matter (82-XX)
82 General topology (54-XX)
73 Algebraic geometry (14-XX)
72 Commutative algebra (13-XX)
69 Functional analysis (46-XX)
64 Operator theory (47-XX)
62 Associative rings and algebras (16-XX)
62 Approximations and expansions (41-XX)
58 Measure and integration (28-XX)
52 Geometry (51-XX)
49 History and biography (01-XX)
40 General and overarching topics; collections (00-XX)
40 Partial differential equations (35-XX)
31 Real functions (26-XX)
29 Manifolds and cell complexes (57-XX)
27 Harmonic analysis on Euclidean spaces (42-XX)
24 Functions of a complex variable (30-XX)
23 Integral equations (45-XX)
17 Algebraic topology (55-XX)
17 Global analysis, analysis on manifolds (58-XX)
15 Difference and functional equations (39-XX)
15 Fluid mechanics (76-XX)
14 Differential geometry (53-XX)
14 Mechanics of particles and systems (70-XX)
14 Mechanics of deformable solids (74-XX)
13 Topological groups, Lie groups (22-XX)
7 Integral transforms, operational calculus (44-XX)
7 Geophysics (86-XX)
6 Sequences, series, summability (40-XX)
6 Abstract harmonic analysis (43-XX)
5 Special functions (33-XX)
5 Optics, electromagnetic theory (78-XX)
2 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 Mathematics education (97-XX)

Citations by Year