×

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,130 Publications (since 1967)
References Indexed: 2,857 Publications with 71,951 References.
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 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.
10 Szeider, Stefan
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 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 Paredaens, Jan
7 Pnueli, Amir
7 Rabani, Yuval
7 Raghavan, Prabhakar
...and 4,119 more Authors
all top 5

Fields

2,853 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)
28 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

Citations contained in zbMATH Open

2,529 Publications have been cited 42,062 times in 28,218 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.
511
1976
A decision-theoretic generalization of on-line learning and an application to boosting. Zbl 0880.68103
Freund, Yoav; Schapire, Robert E.
506
1997
Which problems have strongly exponential complexity? Zbl 1006.68052
Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
495
2001
Optimization, approximation, and complexity classes. Zbl 0765.68036
Papadimitriou, Christos H.; Yannakakis, Mihalis
488
1991
Computing with membranes. Zbl 0956.68055
Păun, Gheorghe
439
2000
Approximation algorithms for combinatorial problems. Zbl 0296.65036
Johnson, David S.
414
1974
Relationships between nondeterministic and deterministic tape complexities. Zbl 0188.33502
Savitch, W. J.
409
1970
On the complexity of \(k\)-SAT. Zbl 0990.68079
Impagliazzo, Russell; Paturi, Ramamohan
389
2001
Probabilistic encryption. Zbl 0563.94013
Goldwasser, Shafi; Micali, Silvio
356
1984
Propositional dynamic logic of regular programs. Zbl 0408.03014
Fischer, Michael J.; Ladner, Richard E.
278
1979
Variable precision rough set model. Zbl 0764.68162
Ziarko, Wojciech
274
1993
Time bounds for selection. Zbl 0278.68033
Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E.
263
1973
Universal classes of hash functions. Zbl 0412.68090
Carter, J. Lawrence; Wegman, Mark N.
262
1979
On the computational power of pushdown automata. Zbl 0207.01701
Aho, A. V.; Ullman, J. D.; Hopcroft, J. E.
246
1970
A data structure for dynamic trees. Zbl 0509.68058
Sleator, Daniel D.; Tarjan, Robert Endre
241
1983
The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029
Lewis, John M.; Yannakakis, Mihalis
233
1980
Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061
Khot, Subhash; Regev, Oded
223
2008
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
219
2009
A theory of type polymorphism in programming. Zbl 0388.68003
Milner, Robin
216
1978
Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). Zbl 0667.68059
Barrington, David A.
202
1989
Parallel program schemata. Zbl 0198.32603
Karp, Richard M.; Miller, Raymond E.
201
1969
Hardness vs randomness. Zbl 0821.68057
Nisan, Noam; Wigderson, Avi
188
1994
Self-testing/correcting with applications to numerical problems. Zbl 0795.68131
Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt
185
1993
On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048
Papadimitriou, Christos H.
184
1994
Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074
Yannakakis, Mihalis
182
1991
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
168
1988
Optimization of LR(k) parsers. Zbl 0264.68032
Aho, A. V.; Ullman, J. D.
167
1972
New hash functions and their use in authentication and set equality. Zbl 0461.68074
Wegman, Mark N.; Carter, J. Lawrence
165
1981
A linear-time algorithm for a special case of disjoint set union. Zbl 0572.68058
Gabow, Harold N.; Tarjan, Robert Endre
163
1985
On uniform circuit complexity. Zbl 0462.68013
Ruzzo, Walter L.
158
1981
Isomorphism of graphs of bounded valence can be tested in polynomial time. Zbl 0493.68064
Luks, Eugene M.
158
1982
The space complexity of approximating the frequency moments. Zbl 0938.68153
Alon, Noga; Matias, Yossi; Szegedy, Mario
150
1999
Handle-rewriting hypergraph grammars. Zbl 0825.68446
Courcelle, Bruno; Engelfriet, Joost; Rozenberg, Grzegorz
149
1993
Fast probabilistic algorithms for Hamiltonian circuits and matchings. Zbl 0437.05040
Angluin, D.; Valiant, L. G.
146
1979
Finding patterns common to a set of strings. Zbl 0454.68108
Angluin, Dana
141
1980
Tree acceptors and some of their applications. Zbl 0212.02901
Doner, John
140
1970
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040
Achlioptas, Dimitris
140
2003
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
135
1990
A faster algorithm computing string edit distances. Zbl 0436.68044
Masek, William J.; Paterson, Michael S.
132
1980
The complexity of optimization problems. Zbl 0652.68040
Krentel, Mark W.
132
1988
What’s decidable about hybrid automata? Zbl 0920.68091
Henzinger, Thomas A.; Kopke, Peter W.; Puri, Anuj; Varaiya, Pravin
131
1998
Maintenance of configurations in the plane. Zbl 0474.68082
Overmars, Mark H.; van Leeuwen, Jan
129
1981
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029
Babai, László; Moran, Shlomo
128
1988
Riemann’s hypothesis and tests for primality. Zbl 0349.68025
Miller, Gary L.
126
1976
Fast algorithms for bin packing. Zbl 0284.68023
Johnson, David S.
126
1974
Space-bounded reducibility among combinatorial problems. Zbl 0317.02039
Jones, Neil D.
122
1975
Randomness is linear in space. Zbl 0846.68041
Nisan, Noam; Zuckerman, David
119
1996
NP-complete scheduling problems. Zbl 0313.68054
Ullman, J. D.
119
1975
The complexity of facets (and some facets of complexity). Zbl 0571.68028
Papadimitriou, C. H.; Yannakakis, M.
119
1984
A framework for solving VLSI graph layout problems. Zbl 0543.68052
Bhatt, Sandeep N.; Leighton, Frank Thompson
114
1984
Structure and complexity of relational queries. Zbl 0511.68073
Chandra, Ashok; Harel, David
114
1982
Relaxing the uniformity and independence assumptions using the concept of fractal dimension. Zbl 0889.68050
Faloutsos, Christos; Kamel, Ibrahim
113
1997
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
112
1992
Groups, the theory of ends, and context-free languages. Zbl 0537.20011
Muller, David E.; Schupp, Paul E.
110
1983
Minimum disclosure proofs of knowledge. Zbl 0656.68109
Brassard, Gilles; Chaum, David; Crépeau, Claude
110
1988
On the complexity of some two-person perfect-information games. Zbl 0383.90112
Schaefer, Thomas J.
108
1978
Reversal-bounded multipushdown machines. Zbl 0309.68043
Baker, Brenda S.; Book, Ronald V.
108
1974
Making data structures persistent. Zbl 0667.68026
Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E.
108
1989
Classifying regular events in symbolic logic. Zbl 0503.68055
Thomas, Wolfgang
108
1982
A tight bound on approximating arbitrary metrics by tree metrics. Zbl 1071.68082
Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal
106
2004
Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Zbl 0263.94019
Amoroso, S.; Patt, Y. N.
102
1972
Decision procedures and expressiveness in the temporal logic of branching time. Zbl 0559.68051
Emerson, E. Allen; Halpern, Joseph Y.
101
1985
An information statistics approach to data stream and communication complexity. Zbl 1074.68022
Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
100
2004
Generalized sequential machine maps. Zbl 0198.03303
Thatcher, J. W.
99
1970
A complete inference system for a class of regular behaviours. Zbl 0562.68065
Milner, Robin
99
1984
Marked directed graphs. Zbl 0238.05109
Commoner, F.; Holt, A. W.; Even, S.; Pnueli, A.
98
1971
Process complexity and effective random tests. Zbl 0273.68036
Schnorr, C. P.
98
1973
Topologically sweeping an arrangement. Zbl 0676.68013
Edelsbrunner, Herbert; Guibas, Leonidas J.
98
1989
Natural proofs. Zbl 0884.68055
Razborov, Alexander A.; Rudich, Steven
96
1997
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
96
2011
Probabilistic construction of deterministic algorithms: approximating packing integer programs. Zbl 0659.90066
Raghavan, Prabhakar
96
1988
Embedding planar graphs in four pages. Zbl 0673.05022
Yannakakis, Mihalis
95
1989
Surpassing the information theoretic bound with fusion trees. Zbl 0795.68049
Fredman, Michael L.; Willard, Dan E.
94
1993
Multiattribute decision making models and methods using intuitionistic fuzzy sets. Zbl 1066.90052
Li, Deng-Feng
92
2005
In search of an easy witness: Exponential time vs. probabilistic polynomial time. Zbl 1059.68047
Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi
92
2002
Automata-theoretic techniques for modal logics of programs. Zbl 0622.03017
Vardi, Moshe Y.; Wolper, Pierre
89
1986
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Zbl 0493.68043
Mahaney, Stephen R.
88
1982
Zero knowledge and the chromatic number. Zbl 0921.68089
Feige, Uriel; Kilian, Joe
88
1998
On the complexity of teaching. Zbl 0939.68770
Goldman, Sally A.; Kearns, Michael J.
87
1995
Almost everywhere high nonuniform complexity. Zbl 0767.68043
Lutz, Jack H.
87
1992
Tesselations with local transformations. Zbl 0246.94037
Richardson, D.
87
1972
Classical complexity and quantum entanglement. Zbl 1093.81012
Gurvits, Leonid
87
2004
Computable queries for relational data bases. Zbl 0456.68128
Chandra, Ashok K.; Harel, David
85
1980
Strong computational lower bounds via parameterized complexity. Zbl 1119.68092
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge
85
2006
Conjunctive-query containment and constraint satisfaction. Zbl 0963.68059
Kolaitis, Phokion G.; Vardi, Moshe Y.
84
2000
Linear unification. Zbl 0371.68013
Paterson, M. S.; Wegman, M. N.
84
1978
Power domains. Zbl 0391.68011
Smyth, M. B.
83
1978
On the computational power of neural nets. Zbl 0826.68104
Siegelmann, Hava T.; Sontag, Eduardo D.
83
1995
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045
Gabber, Ofer; Galil, Zvi
83
1981
Semantics of probabilistic programs. Zbl 0476.68019
Kozen, Dexter
82
1981
Varieties of ordered algebras. Zbl 0337.06008
Bloom, Stephen L.
82
1976
Faster shortest-path algorithms for planar graphs. Zbl 0880.68099
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam
81
1997
Clustering with qualitative information. Zbl 1094.68075
Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony
81
2005
Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Zbl 0155.01802
Thatcher, J. W.
80
1967
Solving reflexive domain equations in a category of complete metric spaces. Zbl 0717.18002
America, Pierre; Rutten, Jan
80
1989
Adherences of languages. Zbl 0471.68052
Boasson, Luc; Nivat, Maurice
80
1980
The average height of binary trees and other simple trees. Zbl 0499.68027
Flajolet, Philippe; Odlyzko, Andrew
79
1982
Optimal shortest path queries in a simple polygon. Zbl 0681.68065
Guibas, Leonidas J.; Hershberger, John
78
1989
Tree-size bounded alternation. Zbl 0445.68034
Ruzzo, Walter L.
77
1980
Real-time language recognition by one-dimensional cellular automata. Zbl 0268.68044
Smith, Alvy Ray III
77
1972
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
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
A physically universal Turing machine. Zbl 07639676
Salo, Ville; Törmä, Ilkka
1
2023
Deterministic non-adaptive contention resolution on a shared channel. Zbl 07639161
De Marco, Gianluca; Kowalski, Dariusz R.; Stachowiak, Grzegorz
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
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
Balanced allocation on hypergraphs. Zbl 1529.90081
Greenhill, Catherine; Mans, Bernard; Pourmiri, Ali
1
2023
Complexity of verification in self-assembly with prebuilt assemblies. Zbl 07695008
Caballero, David; Gomez, Timothy; Schweller, Robert; Wylie, Tim
1
2023
Orthogonal planarity testing of bounded treewidth graphs. Zbl 07466701
Di Giacomo, Emilio; Liotta, Giuseppe; Montecchiani, Fabrizio
11
2022
Induced disjoint paths in AT-free graphs. Zbl 1478.68240
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
5
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
5
2022
Incompressibility of \(H\)-free edge modification problems: towards a dichotomy. Zbl 07466698
Marx, Dániel; Sandeep, R. B.
5
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
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.
3
2022
(In)approximability of maximum minimal FVS. Zbl 1478.68448
Dublois, Louis; Hanaka, Tesshu; Khosravian Ghadikolaei, Mehdi; Lampis, Michael; Melissinos, Nikolaos
2
2022
Many-visits TSP revisited. Zbl 1478.68464
Kowalik, Łukasz; Li, Shaohua; Nadara, Wojciech; Smulewicz, Marcin; Wahlström, Magnus
2
2022
Word equations in non-deterministic linear space. Zbl 1472.68068
Jeż, Artur
2
2022
Length-bounded cuts: proper interval graphs and structural parameters. Zbl 1505.68032
Bentert, Matthias; Heeger, Klaus; Knop, Dušan
2
2022
Complexity of fixed point counting problems in Boolean networks. Zbl 1483.68240
Bridoux, Florian; Durbec, Amélia; Perrot, Kevin; Richard, Adrien
2
2022
Complexity of the multilevel critical node problem. Zbl 1484.91085
Nabli, Adel; Carvalho, Margarida; Hosteins, Pierre
2
2022
Approximating the existential theory of the reals. Zbl 07466700
Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G.
2
2022
Improved distance sensitivity oracles with subcubic preprocessing time. Zbl 1472.68119
Ren, Hanlin
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
Intersection joins under updates. Zbl 07433353
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
Approximate CVP\(_p\) in time \(2^{0.802n}\). Zbl 1478.68449
Eisenbrand, Friedrich; Venzin, Moritz
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
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
Complexity of stability. Zbl 1472.68113
Frei, Fabian; Hemaspaandra, Edith; Rothe, Jörg
1
2022
Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents. Zbl 1476.91070
Zhang, Hanrui
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
Non-essential arcs in phylogenetic networks. Zbl 07526468
Linz, Simone; Semple, Charles
1
2022
Dual domination problems in graphs. Zbl 07526469
Cordasco, Gennaro; Gargano, Luisa; Rescigno, Adele A.
1
2022
Scheduling lower bounds via AND subset sum. Zbl 1483.68142
Abboud, Amir; Bringmann, Karl; Hermelin, Danny; Shabtay, Dvir
1
2022
\(O_n\) is an \(n\)-MCFL. Zbl 1483.68169
Gebhardt, Kilian; Meunier, Frédéric; Salvati, Sylvain
1
2022
Polynomially ambiguous probabilistic automata on restricted languages. Zbl 1483.68156
Bell, Paul C.
1
2022
Computing Weighted Subset Odd Cycle transversals in \(H\)-free graphs. Zbl 07526471
Brettell, Nick; Johnson, Matthew; Paulusma, Daniël
1
2022
Discriminantal subset convolution: refining exterior-algebraic methods for parameterized algorithms. Zbl 1490.68120
Brand, Cornelius
1
2022
Greedy routing and the algorithmic small-world phenomenon. Zbl 07466699
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
12
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
12
2021
The complexity of reachability in parametric Markov decision processes. Zbl 1477.68124
Junges, Sebastian; Katoen, Joost-Pieter; Pérez, Guillermo A.; Winkler, Tobias
11
2021
Sliding window temporal graph coloring. Zbl 1473.68123
Mertzios, George B.; Molter, Hendrik; Zamaraev, Viktor
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.
8
2021
Temporal cliques admit sparse spanners. Zbl 1517.68280
Casteigts, Arnaud; Peters, Joseph G.; Schoeters, Jason
8
2021
Assigning times to minimise reachability in temporal graphs. Zbl 1464.68283
Enright, Jessica; Meeks, Kitty; Skerman, Fiona
8
2021
The hairy ball problem is PPAD-complete. Zbl 1527.68082
Goldberg, Paul W.; Hollender, Alexandros
7
2021
Exploration of dynamic networks: tight bounds on the number of agents. Zbl 1527.68024
Gotoh, Tsuyoshi; Flocchini, Paola; Masuzawa, Toshimitsu; Santoro, Nicola
5
2021
The temporal explorer who returns to the base. Zbl 1515.68221
Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Raptopoulos, Christoforos
5
2021
Preimage problems for deterministic finite automata. Zbl 1464.68148
Berlinkov, Mikhail V.; Ferens, Robert; Szykuła, Marek
4
2021
Bivariate B-splines from convex configurations. Zbl 07365379
Schmitt, Dominique
3
2021
Measuring what matters: a hybrid approach to dynamic programming with treewidth. Zbl 1517.68291
Eiben, Eduard; Ganian, Robert; Hamm, Thekla; Kwon, O-joung
3
2021
On the fast delivery problem with one or two packages. Zbl 1464.68278
Carvalho, Iago A.; Erlebach, Thomas; Papadopoulos, Kleitos
3
2021
Grammar-compressed indexes with logarithmic search time. Zbl 1477.68104
Claude, Francisco; Navarro, Gonzalo; Pacheco, Alejandro
3
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
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
Parameterized \(k\)-clustering: tractability island. Zbl 1477.68132
Fomin, Fedor V.; Golovach, Petr A.; Simonov, Kirill
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
A \(\frac{4}{3}\)-approximation algorithm for the maximum internal spanning tree problem. Zbl 1480.68013
Li, Xingfu; Zhu, Daming; Wang, Lusheng
2
2021
Bisection of bounded treewidth graphs by convolutions. Zbl 1477.68220
Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E.
2
2021
Understanding PPA-completeness. Zbl 1464.68121
Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying
2
2021
Uniform parsing for hyperedge replacement grammars. Zbl 1482.68117
Björklund, Henrik; Drewes, Frank; Ericson, Petter; Starke, Florian
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
Polynomial time approximation schemes for clustering in low highway dimension graphs. Zbl 1527.68260
Feldmann, Andreas Emil; Saulpic, David
1
2021
Speeding-up verification of digital signatures. Zbl 1455.94193
Taleb, Abdul Rahman; Vergnaud, Damien
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
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem. Zbl 1477.68127
Lagerkvist, Victor; Roy, Biman
1
2021
On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Zbl 1480.91023
Caragiannis, Ioannis; Fanelli, Angelo
1
2021
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. Zbl 1505.68018
Kozachinskiy, Alexander; Shen, Alexander
1
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
1
2021
Bidding mechanisms in graph games. Zbl 1480.91053
Avni, Guy; Henzinger, Thomas A.; Žikelić, Đorđe
1
2021
A Turing kernelization dichotomy for structural parameterizations of \(\mathcal{F} \)-minor-free deletion. Zbl 1482.68110
Donkers, Huib; Jansen, Bart M. P.
1
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
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
Reachability relations of timed pushdown automata. Zbl 1484.68079
Clemente, Lorenzo; Lasota, Sławomir
1
2021
The complexity of finding small separators in temporal graphs. Zbl 1436.68265
Zschoche, Philipp; Fluschnik, Till; Molter, Hendrik; Niedermeier, Rolf
32
2020
Temporal vertex cover with a sliding time window. Zbl 1436.68219
Akrida, Eleni C.; Mertzios, George B.; Spirakis, Paul G.; Zamaraev, Viktor
22
2020
Unique end of potential line. Zbl 1461.68086
Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul
13
2020
Counting and enumerating tree-child networks and their subclasses. Zbl 1448.92147
Cardona, Gabriel; Zhang, Louxin
13
2020
Graphs are not universal for online computability. Zbl 1476.03046
Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel
12
2020
Subexponential algorithms for variants of the homomorphism problem in string graphs. Zbl 1435.68243
Okrasa, Karolina; Rzążewski, Paweł
11
2020
2-D Tucker is PPA complete. Zbl 1436.68127
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
10
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
9
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
7
2020
Subexponential algorithm for \(d\)-cluster edge deletion: exception or rule? Zbl 1445.68171
Misra, Neeldhara; Panolan, Fahad; Saurabh, Saket
7
2020
Clique-width and well-quasi-ordering of triangle-free graph classes. Zbl 1442.05184
Dabrowski, Konrad K.; Lozin, Vadim V.; Paulusma, Daniël
6
2020
...and 1425 more Documents
all top 5

Cited by 26,468 Authors

152 Saurabh, Saket
126 Ibarra, Oscar H.
100 Kutrib, Martin
99 Fomin, Fedor V.
98 Niedermeier, Rolf
95 Jain, Sanjay
81 Golovach, Petr A.
75 Stephan, Frank
74 Fernau, Henning
67 Lokshtanov, Daniel
66 Goldreich, Oded
65 Engelfriet, Joost
64 Raman, Venkatesh
63 Hemaspaandra, Lane A.
62 Otto, Friedrich
62 Salomaa, Kai T.
60 Epstein, Leah
60 Pelc, Andrzej
60 Rozenberg, Grzegorz
60 Zehavi, Meirav
59 Ésik, Zoltán
57 Thilikos, Dimitrios M.
56 Gutin, Gregory Z.
56 Paschos, Vangelis Th.
56 Vardi, Moshe Ya’akov
55 Malcher, Andreas
55 Pilipczuk, Marcin L.
55 Rytter, Wojciech
54 Holzer, Markus
53 Demaine, Erik D.
52 Pérez-Jiménez, Mario J.
51 Cai, Jin-Yi
51 Lohrey, Markus
49 Pilipczuk, Michał
49 Rothe, Jörg-Matthias
49 Szeider, Stefan
48 Bodlaender, Hans L.
48 Paulusma, Daniël
47 Chen, Jian-er
47 Komusiewicz, Christian
47 Salomaa, Arto Kustaa
46 Courcelle, Bruno
46 Gottlob, Georg
45 Allender, Eric W.
45 Bose, Prosenjit K.
45 Case, John
45 Marx, Dániel
44 Jansen, Bart M. P.
44 Okhotin, Alexander
44 Păun, Gheorghe
43 Alon, Noga
43 Spirakis, Paul G.
42 Pan, Linqiang
42 Wigderson, Avi
42 Wood, Derick
41 Sau, Ignasi
40 Fellows, Michael Ralph
39 Eppstein, David Arthur
39 Milius, Stefan
39 Panolan, Fahad
39 Peleg, David
38 Adámek, Jiří
38 Chatterjee, Krishnendu
38 Gawrychowski, Paweł
38 Mauri, Giancarlo
38 Sharir, Micha
38 Wang, Jianxin
37 Arvind, Vikraman
37 Crochemore, Maxime
37 Heggernes, Pinar
37 Hromkovič, Juraj
37 Köbler, Johannes
37 Lampis, Michael
37 Lingas, Andrzej
37 Navarro, Gonzalo
37 Papadimitriou, Christos Harilaos
37 Servedio, Rocco A.
36 Chan, Timothy Moon-Yew
36 Italiano, Giuseppe Francesco
36 Kratsch, Stefan
35 Bshouty, Nader H.
35 Eiter, Thomas
35 Ganian, Robert
35 Ito, Takehiro
35 Jiang, Tao
35 Levin, Asaf
35 Munro, J. Ian
34 Lutz, Jack H.
34 Monnot, Jérôme
34 Woeginger, Gerhard
34 Yeo, Anders
33 Fortnow, Lance J.
33 Kowalski, Dariusz R.
33 Vollmer, Heribert
32 Book, Ronald Vernon
32 Culik, Karel II
32 Cygan, Marek
32 Guo, Jiong
32 Karpinski, Marek
32 Mahajan, Meena
...and 26,368 more Authors
all top 5

Cited in 828 Journals

3,715 Theoretical Computer Science
1,614 Journal of Computer and System Sciences
1,084 Information Processing Letters
973 Algorithmica
838 Discrete Applied Mathematics
835 Information and Computation
439 Theory of Computing Systems
377 Information Sciences
346 International Journal of Foundations of Computer Science
287 Acta Informatica
282 SIAM Journal on Computing
266 Artificial Intelligence
223 Mathematical Systems Theory
220 Journal of Combinatorial Optimization
206 Computational Geometry
203 European Journal of Operational Research
190 Computational Complexity
170 Discrete & Computational Geometry
160 Mathematical Programming. Series A. Series B
156 Discrete Mathematics
156 SIAM Journal on Discrete Mathematics
152 Logical Methods in Computer Science
151 Annals of Pure and Applied Logic
146 International Journal of Computer Mathematics
146 Distributed Computing
142 Journal of Discrete Algorithms
136 Journal of Cryptology
136 Machine Learning
128 Operations Research Letters
122 Annals of Mathematics and Artificial Intelligence
120 Journal of Symbolic Computation
116 International Journal of Approximate Reasoning
103 Quantum Information Processing
99 Fuzzy Sets and Systems
99 Natural Computing
93 MSCS. Mathematical Structures in Computer Science
92 Combinatorica
91 RAIRO. Informatique Théorique et Applications
90 RAIRO. Theoretical Informatics and Applications
86 Applied Mathematics and Computation
86 Computers & Operations Research
85 The Journal of Symbolic Logic
84 Soft Computing
83 Journal of Complexity
78 Networks
76 RAIRO, Informatique Théorique
76 Random Structures & Algorithms
75 Discrete Optimization
71 Journal of Machine Learning Research (JMLR)
70 Computing
70 European Journal of Combinatorics
69 International Journal of Computational Geometry & Applications
69 Pattern Recognition
68 Annals of Operations Research
67 Journal of Logical and Algebraic Methods in Programming
65 International Journal of Algebra and Computation
65 Journal of Membrane Computing
64 Formal Aspects of Computing
64 Neural Computation
63 Journal of Automated Reasoning
62 Linear Algebra and its Applications
61 ACM Transactions on Computational Logic
58 Journal of Mathematical Analysis and Applications
57 Computers & Mathematics with Applications
57 Formal Methods in System Design
57 Journal of Scheduling
55 The Annals of Statistics
54 Journal of Combinatorial Theory. Series B
51 Automatica
51 Theory and Practice of Logic Programming
49 International Journal of Theoretical Physics
49 Journal of Optimization Theory and Applications
49 Computer Science Review
48 Designs, Codes and Cryptography
48 Journal of Graph Algorithms and Applications
47 BIT
46 The Journal of Logic and Algebraic Programming
45 Mathematics of Computation
45 Combinatorics, Probability and Computing
43 Journal of Algebra
42 Mathematics of Operations Research
41 Fundamenta Informaticae
40 Cybernetics
39 International Journal of Computer & Information Sciences
39 Journal of Graph Theory
39 Physica D
39 New Generation Computing
38 Journal of Computer Science and Technology
38 Neural Networks
38 Journal of Global Optimization
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
37 Algorithms
36 Studia Logica
36 Cybernetics and Systems Analysis
35 Computational Statistics and Data Analysis
35 Journal of Intelligent and Fuzzy Systems
...and 728 more Journals
all top 5

Cited in 62 Fields

21,385 Computer science (68-XX)
4,551 Combinatorics (05-XX)
3,148 Operations research, mathematical programming (90-XX)
2,968 Mathematical logic and foundations (03-XX)
1,833 Information and communication theory, circuits (94-XX)
1,394 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
872 Statistics (62-XX)
791 Numerical analysis (65-XX)
575 Quantum theory (81-XX)
575 Biology and other natural sciences (92-XX)
525 Probability theory and stochastic processes (60-XX)
511 Group theory and generalizations (20-XX)
417 Number theory (11-XX)
383 Systems theory; control (93-XX)
349 Order, lattices, ordered algebraic structures (06-XX)
346 Convex and discrete geometry (52-XX)
308 Linear and multilinear algebra; matrix theory (15-XX)
308 Dynamical systems and ergodic theory (37-XX)
252 Category theory; homological algebra (18-XX)
205 General algebraic systems (08-XX)
134 Statistical mechanics, structure of matter (82-XX)
129 Ordinary differential equations (34-XX)
123 Calculus of variations and optimal control; optimization (49-XX)
109 General topology (54-XX)
107 Field theory and polynomials (12-XX)
99 Functional analysis (46-XX)
95 Algebraic geometry (14-XX)
82 Commutative algebra (13-XX)
81 Operator theory (47-XX)
78 Approximations and expansions (41-XX)
75 Associative rings and algebras (16-XX)
69 Measure and integration (28-XX)
61 History and biography (01-XX)
60 Geometry (51-XX)
54 Partial differential equations (35-XX)
51 General and overarching topics; collections (00-XX)
40 Manifolds and cell complexes (57-XX)
38 Real functions (26-XX)
35 Harmonic analysis on Euclidean spaces (42-XX)
30 Functions of a complex variable (30-XX)
28 Algebraic topology (55-XX)
24 Integral equations (45-XX)
24 Fluid mechanics (76-XX)
23 Global analysis, analysis on manifolds (58-XX)
23 Mechanics of particles and systems (70-XX)
22 Differential geometry (53-XX)
20 Mechanics of deformable solids (74-XX)
16 Topological groups, Lie groups (22-XX)
15 Difference and functional equations (39-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)
7 Relativity and gravitational theory (83-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)
2 Mathematics education (97-XX)
1 Classical thermodynamics, heat transfer (80-XX)

Citations by Year