×

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,127 Publications (since 1967)
References Indexed: 2,854 Publications with 71,847 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 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 Hsieh, Sun-Yuan
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 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 Klasing, Ralf
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,112 more Authors
all top 5

Fields

2,850 Computer science (68-XX)
313 Mathematical logic and foundations (03-XX)
259 Combinatorics (05-XX)
151 Information and communication theory, circuits (94-XX)
148 Operations research, mathematical programming (90-XX)
88 General and overarching topics; collections (00-XX)
79 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
61 Biology and other natural sciences (92-XX)
58 Numerical analysis (65-XX)
41 Group theory and generalizations (20-XX)
31 Number theory (11-XX)
29 Category theory; homological algebra (18-XX)
27 Probability theory and stochastic processes (60-XX)
27 Statistics (62-XX)
24 Quantum theory (81-XX)
24 Systems theory; control (93-XX)
23 Linear and multilinear algebra; matrix theory (15-XX)
20 Order, lattices, ordered algebraic structures (06-XX)
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,524 Publications have been cited 41,349 times in 27,760 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.
507
1976
A decision-theoretic generalization of on-line learning and an application to boosting. Zbl 0880.68103
Freund, Yoav; Schapire, Robert E.
496
1997
Which problems have strongly exponential complexity? Zbl 1006.68052
Impagliazzo, Russell; Paturi, Ramamohan; Zane, Francis
483
2001
Optimization, approximation, and complexity classes. Zbl 0765.68036
Papadimitriou, Christos H.; Yannakakis, Mihalis
483
1991
Computing with membranes. Zbl 0956.68055
Păun, Gheorghe
413
2000
Approximation algorithms for combinatorial problems. Zbl 0296.65036
Johnson, David S.
410
1974
Relationships between nondeterministic and deterministic tape complexities. Zbl 0188.33502
Savitch, W. J.
401
1970
On the complexity of \(k\)-SAT. Zbl 0990.68079
Impagliazzo, Russell; Paturi, Ramamohan
377
2001
Probabilistic encryption. Zbl 0563.94013
Goldwasser, Shafi; Micali, Silvio
351
1984
Propositional dynamic logic of regular programs. Zbl 0408.03014
Fischer, Michael J.; Ladner, Richard E.
273
1979
Variable precision rough set model. Zbl 0764.68162
Ziarko, Wojciech
267
1993
Universal classes of hash functions. Zbl 0412.68090
Carter, J. Lawrence; Wegman, Mark N.
260
1979
Time bounds for selection. Zbl 0278.68033
Blum, Manuel; Floyd, Robert W.; Pratt, Vaughan; Rivest, Ronald L.; Tarjan, Robert E.
258
1973
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
236
1983
The node-deletion problem for hereditary properties is NP-complete. Zbl 0436.68029
Lewis, John M.; Yannakakis, Mihalis
231
1980
Vertex cover might be hard to approximate to within \(2 - \varepsilon \). Zbl 1133.68061
Khot, Subhash; Regev, Oded
221
2008
On problems without polynomial kernels. Zbl 1192.68288
Bodlaender, Hans L.; Downey, Rodney G.; Fellows, Michael R.; Hermelin, Danny
217
2009
A theory of type polymorphism in programming. Zbl 0388.68003
Milner, Robin
215
1978
Bounded-width polynomial-size branching programs recognize exactly those languages in \(NC^ 1\). Zbl 0667.68059
Barrington, David A.
201
1989
Parallel program schemata. Zbl 0198.32603
Karp, Richard M.; Miller, Raymond E.
198
1969
Hardness vs randomness. Zbl 0821.68057
Nisan, Noam; Wigderson, Avi
183
1994
Expressing combinatorial optimization problems by linear programs. Zbl 0748.90074
Yannakakis, Mihalis
179
1991
Self-testing/correcting with applications to numerical problems. Zbl 0795.68131
Blum, Manuel; Luby, Michael; Rubinfeld, Ronitt
178
1993
On the complexity of the parity argument and other inefficient proofs of existence. Zbl 0806.68048
Papadimitriou, Christos H.
177
1994
Optimization of LR(k) parsers. Zbl 0264.68032
Aho, A. V.; Ullman, J. D.
167
1972
How easy is local search? Zbl 0655.68074
Johnson, David S.; Papadimitriou, Christos H.; Yannakakis, Mihalis
166
1988
New hash functions and their use in authentication and set equality. Zbl 0461.68074
Wegman, Mark N.; Carter, J. Lawrence
163
1981
A linear-time algorithm for a special case of disjoint set union. Zbl 0572.68058
Gabow, Harold N.; Tarjan, Robert Endre
160
1985
Isomorphism of graphs of bounded valence can be tested in polynomial time. Zbl 0493.68064
Luks, Eugene M.
157
1982
On uniform circuit complexity. Zbl 0462.68013
Ruzzo, Walter L.
156
1981
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
The space complexity of approximating the frequency moments. Zbl 0938.68153
Alon, Noga; Matias, Yossi; Szegedy, Mario
143
1999
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
139
1970
Database-friendly random projections: Johnson-Lindenstrauss with binary coins. Zbl 1054.68040
Achlioptas, Dimitris
136
2003
On uniformity within \(NC^ 1\). Zbl 0719.68023
Barrington, David A. Mix; Immerman, Neil; Straubing, Howard
134
1990
The complexity of optimization problems. Zbl 0652.68040
Krentel, Mark W.
131
1988
What’s decidable about hybrid automata? Zbl 0920.68091
Henzinger, Thomas A.; Kopke, Peter W.; Puri, Anuj; Varaiya, Pravin
130
1998
A faster algorithm computing string edit distances. Zbl 0436.68044
Masek, William J.; Paterson, Michael S.
130
1980
Maintenance of configurations in the plane. Zbl 0474.68082
Overmars, Mark H.; van Leeuwen, Jan
128
1981
Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. Zbl 0652.03029
Babai, László; Moran, Shlomo
126
1988
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.
121
1975
Riemann’s hypothesis and tests for primality. Zbl 0349.68025
Miller, Gary L.
121
1976
The complexity of facets (and some facets of complexity). Zbl 0571.68028
Papadimitriou, C. H.; Yannakakis, M.
119
1984
Randomness is linear in space. Zbl 0846.68041
Nisan, Noam; Zuckerman, David
117
1996
NP-complete scheduling problems. Zbl 0313.68054
Ullman, J. D.
117
1975
Relaxing the uniformity and independence assumptions using the concept of fractal dimension. Zbl 0889.68050
Faloutsos, Christos; Kamel, Ibrahim
113
1997
Structure and complexity of relational queries. Zbl 0511.68073
Chandra, Ashok; Harel, David
112
1982
A framework for solving VLSI graph layout problems. Zbl 0543.68052
Bhatt, Sandeep N.; Leighton, Frank Thompson
112
1984
Groups, the theory of ends, and context-free languages. Zbl 0537.20011
Muller, David E.; Schupp, Paul E.
110
1983
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
110
1992
Minimum disclosure proofs of knowledge. Zbl 0656.68109
Brassard, Gilles; Chaum, David; Crépeau, Claude
109
1988
Classifying regular events in symbolic logic. Zbl 0503.68055
Thomas, Wolfgang
108
1982
Reversal-bounded multipushdown machines. Zbl 0309.68043
Baker, Brenda S.; Book, Ronald V.
106
1974
Making data structures persistent. Zbl 0667.68026
Driscoll, James R.; Sarnak, Neil; Sleator, Daniel D.; Tarjan, Robert E.
105
1989
A tight bound on approximating arbitrary metrics by tree metrics. Zbl 1071.68082
Fakcharoenphol, Jittat; Rao, Satish; Talwar, Kunal
103
2004
On the complexity of some two-person perfect-information games. Zbl 0383.90112
Schaefer, Thomas J.
103
1978
Decision procedures and expressiveness in the temporal logic of branching time. Zbl 0559.68051
Emerson, E. Allen; Halpern, Joseph Y.
101
1985
Decision procedures for surjectivity and injectivity of parallel maps for tessellation structures. Zbl 0263.94019
Amoroso, S.; Patt, Y. N.
100
1972
A complete inference system for a class of regular behaviours. Zbl 0562.68065
Milner, Robin
99
1984
Generalized sequential machine maps. Zbl 0198.03303
Thatcher, J. W.
99
1970
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.
97
1989
Marked directed graphs. Zbl 0238.05109
Commoner, F.; Holt, A. W.; Even, S.; Pnueli, A.
97
1971
Probabilistic construction of deterministic algorithms: approximating packing integer programs. Zbl 0659.90066
Raghavan, Prabhakar
96
1988
Infeasibility of instance compression and succinct PCPs for NP. Zbl 1233.68144
Fortnow, Lance; Santhanam, Rahul
96
2011
Embedding planar graphs in four pages. Zbl 0673.05022
Yannakakis, Mihalis
94
1989
An information statistics approach to data stream and communication complexity. Zbl 1074.68022
Bar-Yossef, Ziv; Jayram, T. S.; Kumar, Ravi; Sivakumar, D.
94
2004
Surpassing the information theoretic bound with fusion trees. Zbl 0795.68049
Fredman, Michael L.; Willard, Dan E.
93
1993
Multiattribute decision making models and methods using intuitionistic fuzzy sets. Zbl 1066.90052
Li, Deng-Feng
91
2005
Automata-theoretic techniques for modal logics of programs. Zbl 0622.03017
Vardi, Moshe Y.; Wolper, Pierre
89
1986
Natural proofs. Zbl 0884.68055
Razborov, Alexander A.; Rudich, Steven
89
1997
In search of an easy witness: Exponential time vs. probabilistic polynomial time. Zbl 1059.68047
Impagliazzo, Russell; Kabanets, Valentine; Wigderson, Avi
89
2002
Sparse complete sets for NP: solution of a conjecture of Berman and Hartmanis. Zbl 0493.68043
Mahaney, Stephen R.
88
1982
On the complexity of teaching. Zbl 0939.68770
Goldman, Sally A.; Kearns, Michael J.
87
1995
Zero knowledge and the chromatic number. Zbl 0921.68089
Feige, Uriel; Kilian, Joe
87
1998
Classical complexity and quantum entanglement. Zbl 1093.81012
Gurvits, Leonid
86
2004
Almost everywhere high nonuniform complexity. Zbl 0767.68043
Lutz, Jack H.
86
1992
Tesselations with local transformations. Zbl 0246.94037
Richardson, D.
85
1972
Computable queries for relational data bases. Zbl 0456.68128
Chandra, Ashok K.; Harel, David
85
1980
Linear unification. Zbl 0371.68013
Paterson, M. S.; Wegman, M. N.
84
1978
Conjunctive-query containment and constraint satisfaction. Zbl 0963.68059
Kolaitis, Phokion G.; Vardi, Moshe Y.
83
2000
Strong computational lower bounds via parameterized complexity. Zbl 1119.68092
Chen, Jianer; Huang, Xiuzhen; Kanj, Iyad A.; Xia, Ge
83
2006
Explicit constructions of linear-sized superconcentrators. Zbl 0487.05045
Gabber, Ofer; Galil, Zvi
82
1981
Varieties of ordered algebras. Zbl 0337.06008
Bloom, Stephen L.
82
1976
Semantics of probabilistic programs. Zbl 0476.68019
Kozen, Dexter
81
1981
Clustering with qualitative information. Zbl 1094.68075
Charikar, Moses; Guruswami, Venkatesan; Wirth, Anthony
80
2005
Faster shortest-path algorithms for planar graphs. Zbl 0880.68099
Henzinger, Monika R.; Klein, Philip; Rao, Satish; Subramanian, Sairam
80
1997
On the computational power of neural nets. Zbl 0826.68104
Siegelmann, Hava T.; Sontag, Eduardo D.
79
1995
Characterizing derivation trees of context-free grammars through a generalization of finite automata theory. Zbl 0155.01802
Thatcher, J. W.
79
1967
Solving reflexive domain equations in a category of complete metric spaces. Zbl 0717.18002
America, Pierre; Rutten, Jan
79
1989
Power domains. Zbl 0391.68011
Smyth, M. B.
79
1978
The average height of binary trees and other simple trees. Zbl 0499.68027
Flajolet, Philippe; Odlyzko, Andrew
78
1982
Adherences of languages. Zbl 0471.68052
Boasson, Luc; Nivat, Maurice
77
1980
Tree-size bounded alternation. Zbl 0445.68034
Ruzzo, Walter L.
77
1980
Optimal shortest path queries in a simple polygon. Zbl 0681.68065
Guibas, Leonidas J.; Hershberger, John
76
1989
Real-time language recognition by one-dimensional cellular automata. Zbl 0268.68044
Smith, Alvy Ray III
76
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
Balanced allocation on hypergraphs. Zbl 07730238
Greenhill, Catherine; Mans, Bernard; Pourmiri, Ali
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
A physically universal Turing machine. Zbl 07639676
Salo, Ville; Törmä, Ilkka
1
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 07601249
Saurabh, Saket; Zehavi, Meirav
1
2023
Complexity of verification in self-assembly with prebuilt assemblies. Zbl 07695008
Caballero, David; Gomez, Timothy; Schweller, Robert; Wylie, Tim
1
2023
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 07695019
Jacob, Ashwin; Majumdar, Diptapriyo; Raman, Venkatesh
1
2023
Orthogonal planarity testing of bounded treewidth graphs. Zbl 07466701
Di Giacomo, Emilio; Liotta, Giuseppe; Montecchiani, Fabrizio
10
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
Induced disjoint paths in AT-free graphs. Zbl 1478.68240
Golovach, Petr A.; Paulusma, Daniël; van Leeuwen, Erik Jan
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
Word equations in non-deterministic linear space. Zbl 1472.68068
Jeż, Artur
2
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
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
An improved algorithm for the Steiner tree problem with bounded edge-length. Zbl 1472.68111
Chen, Chi-Yeh; Hsieh, Sun-Yuan
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
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
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
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
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
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
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
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
9
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
Assigning times to minimise reachability in temporal graphs. Zbl 1464.68283
Enright, Jessica; Meeks, Kitty; Skerman, Fiona
7
2021
The hairy ball problem is PPAD-complete. Zbl 1527.68082
Goldberg, Paul W.; Hollender, Alexandros
7
2021
Temporal cliques admit sparse spanners. Zbl 1517.68280
Casteigts, Arnaud; Peters, Joseph G.; Schoeters, Jason
6
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
Exploration of dynamic networks: tight bounds on the number of agents. Zbl 1527.68024
Gotoh, Tsuyoshi; Flocchini, Paola; Masuzawa, Toshimitsu; Santoro, Nicola
5
2021
Preimage problems for deterministic finite automata. Zbl 1464.68148
Berlinkov, Mikhail V.; Ferens, Robert; Szykuła, Marek
4
2021
On the fast delivery problem with one or two packages. Zbl 1464.68278
Carvalho, Iago A.; Erlebach, Thomas; Papadopoulos, Kleitos
3
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
Understanding PPA-completeness. Zbl 1464.68121
Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying
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
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
Bisection of bounded treewidth graphs by convolutions. Zbl 1477.68220
Eiben, Eduard; Lokshtanov, Daniel; Mouawad, Amer E.
2
2021
Reducing graph transversals via edge contractions. Zbl 1477.68239
Lima, Paloma T.; dos Santos, Vinicius F.; Sau, Ignasi; Souza, Uéverton S.
2
2021
An efficiently computable characterization of stability and instability for linear cellular automata. Zbl 1527.68136
Dennunzio, Alberto; Formenti, Enrico; Grinberg, Darij; Margara, Luciano
2
2021
Lattice-based weak-key analysis on single-server outsourcing protocols of modular exponentiations and basic countermeasures. Zbl 1517.68107
Zheng, Yunhai; Tian, Chengliang; Zhang, Hanlin; Yu, Jia; Li, Fengjun
2
2021
Uniform parsing for hyperedge replacement grammars. Zbl 1482.68117
Björklund, Henrik; Drewes, Frank; Ericson, Petter; Starke, Florian
2
2021
Grammar-compressed indexes with logarithmic search time. Zbl 1477.68104
Claude, Francisco; Navarro, Gonzalo; Pacheco, Alejandro
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
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
Speeding-up verification of digital signatures. Zbl 1455.94193
Taleb, Abdul Rahman; Vergnaud, Damien
1
2021
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem. Zbl 1477.68127
Lagerkvist, Victor; Roy, Biman
1
2021
On approximate pure Nash equilibria in weighted congestion games with polynomial latencies. Zbl 1480.91023
Caragiannis, Ioannis; Fanelli, Angelo
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
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
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
Polynomial time approximation schemes for clustering in low highway dimension graphs. Zbl 1527.68260
Feldmann, Andreas Emil; Saulpic, David
1
2021
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited. Zbl 1505.68018
Kozachinskiy, Alexander; Shen, Alexander
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
21
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
12
2020
Graphs are not universal for online computability. Zbl 1476.03046
Downey, Rodney; Harrison-Trainor, Matthew; Kalimullin, Iskander; Melnikov, Alexander; Turetsky, Daniel
12
2020
2-D Tucker is PPA complete. Zbl 1436.68127
Aisenberg, James; Bonet, Maria Luisa; Buss, Sam
10
2020
Subexponential algorithms for variants of the homomorphism problem in string graphs. Zbl 1435.68243
Okrasa, Karolina; Rzążewski, Paweł
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
8
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
Hitting minors on bounded treewidth graphs. III. Lower bounds. Zbl 1435.68121
Baste, Julien; Sau, Ignasi; Thilikos, Dimitrios M.
6
2020
A trichotomy for regular simple path queries on graphs. Zbl 1436.68131
Bagan, Guillaume; Bonifati, Angela; Groz, Benoit
5
2020
...and 1426 more Documents
all top 5

Cited by 26,119 Authors

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

Cited in 822 Journals

3,670 Theoretical Computer Science
1,595 Journal of Computer and System Sciences
1,068 Information Processing Letters
964 Algorithmica
828 Discrete Applied Mathematics
827 Information and Computation
439 Theory of Computing Systems
361 Information Sciences
346 International Journal of Foundations of Computer Science
287 Acta Informatica
274 SIAM Journal on Computing
265 Artificial Intelligence
223 Mathematical Systems Theory
220 Journal of Combinatorial Optimization
201 Computational Geometry
198 European Journal of Operational Research
190 Computational Complexity
168 Discrete & Computational Geometry
157 Mathematical Programming. Series A. Series B
156 SIAM Journal on Discrete Mathematics
153 Discrete Mathematics
150 Logical Methods in Computer Science
149 Annals of Pure and Applied Logic
145 International Journal of Computer Mathematics
145 Distributed Computing
141 Journal of Discrete Algorithms
136 Journal of Cryptology
136 Machine Learning
125 Operations Research Letters
122 Annals of Mathematics and Artificial Intelligence
117 Journal of Symbolic Computation
113 International Journal of Approximate Reasoning
103 Quantum Information Processing
99 Natural Computing
95 Fuzzy Sets and Systems
93 MSCS. Mathematical Structures in Computer Science
92 Combinatorica
91 RAIRO. Informatique Théorique et Applications
90 RAIRO. Theoretical Informatics and Applications
85 Applied Mathematics and Computation
85 The Journal of Symbolic Logic
85 Computers & Operations Research
84 Soft Computing
83 Journal of Complexity
78 Networks
76 RAIRO, Informatique Théorique
76 Random Structures & Algorithms
75 Discrete Optimization
70 Computing
69 European Journal of Combinatorics
69 International Journal of Computational Geometry & Applications
69 Pattern Recognition
68 Annals of Operations Research
66 Journal of Logical and Algebraic Methods in Programming
65 International Journal of Algebra and Computation
64 Formal Aspects of Computing
64 Neural Computation
64 Journal of Membrane Computing
63 Journal of Automated Reasoning
62 Journal of Machine Learning Research (JMLR)
61 Linear Algebra and its Applications
61 ACM Transactions on Computational Logic
58 Journal of Mathematical Analysis and Applications
57 Formal Methods in System Design
56 Journal of Scheduling
55 The Annals of Statistics
54 Journal of Combinatorial Theory. Series B
52 Computers & Mathematics with Applications
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
47 BIT
47 Journal of Graph Algorithms and Applications
45 Mathematics of Computation
45 Combinatorics, Probability and Computing
43 Journal of Algebra
42 Mathematics of Operations Research
40 Cybernetics
40 The Journal of Logic and Algebraic Programming
39 International Journal of Computer & Information Sciences
39 Journal of Graph Theory
39 New Generation Computing
39 Fundamenta Informaticae
38 Journal of Computer Science and Technology
38 Journal of Global Optimization
38 Journal of Applied Logic
37 Journal of Logic, Language and Information
37 Journal of Applied Non-Classical Logics
37 The Electronic Journal of Combinatorics
37 Algorithms
36 Studia Logica
36 Neural Networks
36 Cybernetics and Systems Analysis
35 Physica D
35 Computational Statistics and Data Analysis
35 Journal of Intelligent and Fuzzy Systems
34 Mathematical Logic Quarterly (MLQ)
...and 722 more Journals
all top 5

Cited in 62 Fields

21,049 Computer science (68-XX)
4,449 Combinatorics (05-XX)
3,104 Operations research, mathematical programming (90-XX)
2,928 Mathematical logic and foundations (03-XX)
1,800 Information and communication theory, circuits (94-XX)
1,368 Game theory, economics, finance, and other social and behavioral sciences (91-XX)
849 Statistics (62-XX)
780 Numerical analysis (65-XX)
559 Quantum theory (81-XX)
555 Biology and other natural sciences (92-XX)
517 Probability theory and stochastic processes (60-XX)
505 Group theory and generalizations (20-XX)
409 Number theory (11-XX)
375 Systems theory; control (93-XX)
342 Order, lattices, ordered algebraic structures (06-XX)
341 Convex and discrete geometry (52-XX)
299 Dynamical systems and ergodic theory (37-XX)
298 Linear and multilinear algebra; matrix theory (15-XX)
247 Category theory; homological algebra (18-XX)
200 General algebraic systems (08-XX)
123 Statistical mechanics, structure of matter (82-XX)
121 Calculus of variations and optimal control; optimization (49-XX)
117 Ordinary differential equations (34-XX)
106 Field theory and polynomials (12-XX)
105 General topology (54-XX)
95 Functional analysis (46-XX)
94 Algebraic geometry (14-XX)
82 Commutative algebra (13-XX)
81 Operator theory (47-XX)
75 Associative rings and algebras (16-XX)
75 Approximations and expansions (41-XX)
69 Measure and integration (28-XX)
59 History and biography (01-XX)
59 Geometry (51-XX)
52 Partial differential equations (35-XX)
50 General and overarching topics; collections (00-XX)
39 Manifolds and cell complexes (57-XX)
36 Real functions (26-XX)
35 Harmonic analysis on Euclidean spaces (42-XX)
29 Functions of a complex variable (30-XX)
27 Algebraic topology (55-XX)
24 Integral equations (45-XX)
23 Global analysis, analysis on manifolds (58-XX)
22 Differential geometry (53-XX)
22 Mechanics of particles and systems (70-XX)
22 Fluid mechanics (76-XX)
19 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)
8 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