OOIR: Observatory of International Research

Papers

(The median citation count of Journal of Computer and System Sciences is 1. The table below lists those papers that are above that threshold based on CrossRef citation counts [max. 250 papers]. The publications cover those that have been published in the past four years, i.e., from 2021-02-01 to 2025-02-01.)

Article	Citations
Bounded incentives in manipulating the probabilistic serial rule	24
Solving problems on generalized convex graphs via mim-width	21
The maximal coordination principle in regulatory Boolean networks	19
SAT backdoors: Depth beats size	16
Selective monitoring	14
Editorial Board	13
A 43-approximati	13
Exploration of dynamic networks: Tight bounds on the number of agents	12
The temporal explorer who returns to the base	12
Clocked population protocols	12
A 4 + ϵ approximation for k-connected subgraphs	11
Special issue on Algorithmic Theory of Dynamic Networks and Its Applications – Preface	10
Improved prophet inequalities for combinatorial welfare maximization with (approximately) subadditive agents	9
Editorial Board	8
Deterministic non-adaptive contention resolution on a shared channel	8
Etherless Ethereum tokens: Simulating native tokens in Ethereum	7
Online bin covering with limited migration	7
Reducing the vertex cover number via edge contractions	7
Parameterised temporal exploration problems	7
O is an n-MCFL	6
Latency, capacity, and distributed minimum spanning trees	6
Covering metric spaces by few trees	6
Parameterized complexity of categorical clustering with size constraints	6
Assigning times to minimise reachability in temporal graphs	6
Complexity of inverse constraint problems and a dichotomy for the inverse satisfiability problem	6

A maximum clique based approximation algorithm for wireless link scheduling under SINR model	5
Minimum separator reconfiguration	5
Corrigendum to “Prediction, learning, uniform convergence, and scale-sensitive dimensions” [J. Comput. Syst. Sci. 56 (2) (1998) 174–190]	5
The satisfiability problem for a quantitative fragment of PCTL	5
Speeding-up verification of digital signatures	5
Bivariate B-splines from convex configurations	5
Polynomially ambiguous probabilistic automata on restricted languages	5
Measuring what matters: A hybrid approach to dynamic programming with treewidth	5
Editorial Board	4
Detours in directed graphs	4
Building squares with optimal state complexity in restricted active self-assembly	4
Labeled sample compression schemes for complexes of oriented matroids	4
Special Issue on the 1st Symposium on Algorithmic Foundations of Dynamic Networks (SAND 2022)	4
On finding separators in temporal split and permutation graphs	4
The 2CNF Boolean formula satisfiability problem and the linear space hypothesis	4
Preprocessing vertex-deletion problems: Characterizing graph properties by low-rank adjacencies	4
Approximate CVP in time 20.802	4
Searching by heterogeneous agents	4
Priority Promotion with Parysian flair	4
The complexity of binary matrix completion under diameter constraints	4
Space characterizations of complexity measures and size-space trade-offs in propositional proof systems	4
Lifting query complexity to time-space complexity for two-way finite automata	4
Bankrupting Sybil despite churn	4
A new temporal interpretation of cluster editing	4
PAC learning halfspaces in non-interactive local differential privacy model with public unlabeled data	4
Undecidability of the speed positiveness problem in reversible and complete Turing machines	3
A dichotomy for bounded degree graph homomorphisms with nonnegative weights	3
Bidding mechanisms in graph games	3
46th International Colloquium on Automata, Languages and Programming (ICALP 2019) - Track C: Foundations of networks and multi-agent systems	3
Single-source shortest paths and strong connectivity in dynamic planar graphs	3
Greedy routing and the algorithmic small-world phenomenon	3
Complexity of verification in self-assembly with prebuilt assemblies	3
Editorial Board	3
Editorial – Special issue on Concurrency Theory (CONCUR 2018)	3
Analytic methods for reachability problems	3
Closure and nonclosure properties of the classes of compressible and rankable sets	3
Editorial Board	3
Modular SAT-based techniques for reasoning tasks in team semantics	3
Largest common prefix of a regular tree language	3
Quantum random access stored-program machines	3
Bisection of bounded treewidth graphs by convolutions	3
On the parameterized complexity of Grid Contraction	3
Uniform parsing for hyperedge replacement grammars	3
Approximating the existential theory of the reals	3
Efficiently enumerating hitting sets of hypergraphs arising in data profiling	3
Reachability relations of timed pushdown automata	3
Parameterized complexity of graph planarity with restricted cyclic orders	2
The impact of state merging on predictive accuracy in probabilistic tree automata: Dietze's conjecture revisited	2
Editorial Board	2
Mengerian graphs: Characterization and recognition	2

Descriptive complexity of #P functions: A new perspective	2
Computing Weighted Subset Odd Cycle Transversals in H-free graphs	2
Addition machines, automatic functions and open problems of Floyd and Knuth	2
Complexity of fixed point counting problems in Boolean networks	2
Performance modeling and analysis for randomly walking mobile users with Markov chains	2
Faster compressed quadtrees	2
Resource-bounded Kolmogorov complexity provides an obstacle to soficness of multidimensional shifts	2
How heavy independent sets help to find arborescences with many leaves in DAGs	2
A linear algorithm for radio k-coloring of powers of paths having small diameters	2
Polynomial anonymous dynamic distributed computing without a unique leader	2
Almost optimal query algorithm for hitting set using a subset query	2
Preimage problems for deterministic finite automata	2
An extension of the Moran process using type-specific connection graphs	2
Deep kernelization for the Tree Bisection and Reconnection (TBR) distance in phylogenetics	2
Editorial Board	2
Succinct representation for (non)deterministic finite automata	2
The possible winner with uncertain weights problem	2
Editorial Board	2
Arithmetical complexity of the language of generic limit sets of cellular automata	2
Serial and parallel kernelization of Multiple Hitting Set parameterized by the Dilworth number, implemented on the GPU	2
Intersection joins under updates	2
A modeling approach for estimating performance and energy consumption of storage systems	2
On kernels for d-path vertex cover	2
Improved distance sensitivity oracles with subcubic preprocessing time	2
On coresets for fair clustering in metric and Euclidean spaces and their applications	2
Algorithms for hierarchical and semi-partitioned parallel scheduling	2
Approximation algorithms for clustering with dynamic points	2
Complexity of the multilevel critical node problem	1
An almost optimal approximation algorithm for monotone submodular multiple knapsack	1
A secure searchable encryption scheme for cloud using hash-based indexing	1
Packing arc-disjoint cycles in oriented graphs	1
Automatic Kolmogorov complexity, normality, and finite-state dimension revisited	1
Reducing graph transversals via edge contractions	1
Fine-grained complexity of rainbow coloring and its variants	1
A Turing kernelization dichotomy for structural parameterizations of F-Minor-	1
Your rugby mates don't need to know your colleagues: Triadic closure with edge colors	1
Grammar-compressed indexes with logarithmic search time	1
Pushing the Online Boolean Matrix-vector Multiplication conjecture off-line and identifying its easy cases	1
The complexity of online bribery in sequential elections	1
Editorial Board	1
On approximate pure Nash equilibria in weighted congestion games with polynomial latencies	1
Communicating finite-state machines, first-order logic, and star-free propositional dynamic logic	1
Medians in median graphs and their cube complexes in linear time	1
Galactic token sliding	1
Regularizing conjunctive features for classification	1
Absolute convergence and error thresholds in non-active adaptive sampling	1
The tree-generative capacity of combinatory categorial grammars	1
(In)approximability of maximum minimal FVS	1
Editorial Board	1
Dual domination problems in graphs	1
Length-bounded cuts: Proper interval graphs and structural parameters	1
The Projection Games Conjecture and the hardness of approximation of super-SAT and related problems	1
Decidable problems in substitution shifts	1
Incompressibility of H-free edge modification problems: Towards a dichotomy	1
Block trees	1
Nominal syntax with atom substitutions	1
Editorial Board	1
Parameterized complexity of multi-node hubs	1
Editorial Board	1
Additive approximation algorithms for modularity maximization	1