Theoretical Computer Science

Article	Citations
An optimal algorithm for 2-bounded delay buffer management with lookahead	47
A 5k-vertex kernel for 3-path vertex cover	46
Closed subsets in Bishop topological groups	38
A new dynamic programming algorithm for the simplified partial digest problem	38
An algorithm for the secure total domination problem in proper interval graphs	35
CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN	32
A generalization of a theorem of Rothschild and van Lint	30
New (k,l,m)-verifiable multi-secret sharing schemes based on XTR public key system	30
Finer-grained reductions in fine-grained hardness of approximation	22
Editorial Board	20
A data structure for substring-substring LCS length queries	19
Editorial Board	19
Editorial Board	18
Improved upper bound for sorting permutations by prefix transpositions	17
Editorial Board	17
Complexity issues for timeline-based planning over dense time under future and minimal semantics	17
Editorial Board	17
Oracle separations for non-adaptive collapse-free quantum computing	16
A parametric worst-case approach to fairness in cooperative games with transferable utility	16
An array P system based on a new variant of pure 2D context-free grammars	16
An algorithmic construction of union-intersection-bounded families	16
Editorial Board	16
Network control games played on graphs	15
Preface	15
Factorisation in the semiring of finite dynamical systems	15

Editorial Board	15
The parameterized complexity of welfare guarantees in Schelling segregation	14
Complexity and algorithms for neighbor-sum-2-distinguishing {1,3}-edge-weighting of graphs	14
Editorial Board	14
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	14
On 1-planar graphs with bounded cop-number	14
On the binary digits of n and n2	13
Wildcarded identity-based encryption from lattices	13
Sublinear P system solutions to NP-complete problems	13
Notes on Smyth-completes and local Yoneda-completes	13
How real is incomputability in physics?	13
Distributed coloring and the local structure of unit-disk graphs	13
Maximal degenerate palindromes with gaps and mismatches	13
Call admission problems on grids with advice	12
Axiomatising weak bisimulation congruences over CCS with left merge and communication merge	12
A linkable ring signature scheme with unconditional anonymity in the standard model	12
Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation	12
Cellular automata and bootstrap percolation	12
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity	12
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency	12
A linear time algorithm for connected p-centdian problem on block graphs	12
Integer k-matching preclusion of some interconnection networks	12
Three remarks on W graphs	12
Towards a general methodology for formal verification on spiking neural P systems	11
Algorithms for energy conservation in heterogeneous data centers	11
Approximation algorithms for maximum weighted throughput on unrelated machines	11
Physical ZKP protocols for Nurimisaki and Kurodoko	11
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	11
Updatable searchable symmetric encryption: Definitions and constructions	11
On the power of threshold-based algorithms for detecting cycles in the CONGEST model	11
Reliability evaluation of complete graph-based recursive networks	11
Deterministic rendezvous in infinite trees	11
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	11
Linear Programming complementation	10
The computational complexity of forced capture Hnefatafl	10
Powers of low rank sparse matrices	10
On some FPT problems without polynomial Turing compressions	10
Investigation of E-voting system using face recognition using convolutional neural network (CNN)	10
A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem	10
Editorial Board	10
Editorial Board	10
Polynomial kernels for paw-free edge modification problems	10
Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	10
Gacs – Kucera theorem	10
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	10
Robustly reusable fuzzy extractor from isogeny	10
Editorial Board	9
Editorial Board	9
Editorial Board	9
On computable numbers, with an application to the Druckproblem	9

Embedding algorithm of spined cube into grid structure and its wirelength computation	9
NP-hardness of m-dimensional weighted matching problems	9
Connectivity and diagnosability of the complete Josephus cube networks under h-extra fault-tolerant model	9
The impact of core constraints on truthful bidding in combinatorial auctions	9
On the complexity of nucleolus computation for bipartite b-matching games	9
New approximation algorithms for RNA secondary structures prediction problems by local search	9
On additive approximate submodularity	9
Complexity of Scorpion Solitaire and applications to Klondike	9
Disjoint paths and connected subgraphs for H-free graphs	9
A Myhill-Nerode theorem for register automata and symbolic trace languages	9
Upper powerdomains of quasicontinuous dcpos	9
Enumeration of subtrees and BC-subtrees with maximum degree no more than k in trees	8
The classes PPA-k: Existence from arguments modulo k	8
The existence and efficiency of PMMS allocations	8
Modelling of DNA mismatch repair with a reversible process calculus	8
Editorial Board	8
Relating randomized right-hand sides to communicating rewriting rules	8
Near-optimal clustering in the k-machine model	8
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	8
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	8
On minimal critical exponent of balanced sequences	8
A substructure based lower bound for eternal vertex cover number	8
Editorial Board	8
Bisimilarity on Basic Parallel Processes	8
Lower bounds for the sum of small-size algebraic branching programs	8
Algebraic properties and transformations of monographs	8
Generative abstraction of Markov population processes	8
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	8
Generating Java code pairing with ChatGPT	8
On the complexity of winner determination and strategic control in conditional approval voting	8
The balanced connected subgraph problem for geometric intersection graphs	8
On the existence of EFX (and Pareto-optimal) allocations for binary chores	8
Nearly k-universal words – Investigating a part of Simon's congruence	8
Building bridges – Honoring Nataša Jonoska on the occasion of her 60th birthday	8
Identity-based matchmaking encryption with stronger security and instantiation on lattices	8
Algorithmic results in secure total dominating sets on graphs	8
Computational complexity of normalizing constants for the product of determinantal point processes	8
Grouped domination parameterized by vertex cover, twin cover, and beyond	8
Eliciting truthful reports with partial signals in repeated games	7
Editorial Board	7
An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint	7
Securing data in the cloud using pairing-free inner product functional encryption with unbounded vector size	7
A new fast root-finder for black box polynomials	7
Improved algorithms for bandit with graph feedback via regret decomposition	7
Protocols with constant local storage and unreliable communication	7
On a vertex-capturing game	7
A simple rounding scheme for multistage optimization	7
An approximate cost recovery scheme for the k-product facility location game with penalties	7
Cascade products and Wheeler automata	7
Editorial Board	7
On the complexity of local-equitable coloring of graphs	7
Asynchronous fully-decentralized SGD in the cluster-based model	7
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	7
Complexity results on register context-free grammars and related formalisms	7
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	7
Range minimum queries in minimal space	7
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	7
Boundary sketching with asymptotically optimal distance and rotation	7
(k,p)-planarity: A relaxation of hybrid planarity	7
The g-component connectivity of graphs	7
Disjunctive sums of quasi-nimbers	7
Component conditional fault tolerance of hierarchical folded cubic networks	7
Threshold-based network structural dynamics	7
How bad is the merger paradox?	7
A categorical model for organic chemistry	7
Taming the knight's tour: Minimizing turns and crossings	7
Online coloring of disk graphs	7
Improved unbounded inner-product functional encryption	6
Certification of an exact worst-case self-stabilization time	6
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	6
Exploring the gap between treedepth and vertex cover through vertex integrity	6
Editorial Board	6
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	6
Editorial Board	6
Approximation algorithm for prize-collecting sweep cover with base stations	6
Editorial Board	6
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	6
Fixed points and attractors of reactantless and inhibitorless reaction systems	6
Cutting bamboo down to size	6
Extensional proofs in a propositional logic modulo isomorphisms	6

Mutual witness Gabriel drawings of complete bipartite graphs	6
Unified graphical co-modeling, analysis and verification of cyber-physical systems by combining AADL and Simulink/Stateflow	6
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	6
TCS special issue: Combinatorics on Words – WORDS 2021	6
Editorial Board	6
Editorial Board	6
Order based algorithms for the core maintenance problem on edge-weighted graphs	6
Differential logical relations, part II increments and derivatives	6
On algorithmic applications of sim-width and mim-width of (H1,H2)-free graphs	6
Multi-stage Proof-of-Works: Properties and vulnerabilities	6
Capacity planning for dependable services	6
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	6
Verifiable Crowd Computing: Coping with bounded rationality	6
Languages generated by numerical P systems with thresholds	6
Editorial Board	6
In memory of Jérôme Monnot	6
Almost envy-freeness for groups: Improved bounds via discrepancy theory	6
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	6
Enhancing fault tolerance of balanced hypercube networks by the edge partition method	6
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	6
Optimal L-algorithms for rendezvous of asynchronous mobile robots with extern	5
Approximating power node-deletion problems	5
Visibility extension via reflection	5
On the power of local graph expansion grammars with and without additional restrictions	5
Efficient and reliable post-quantum authentication	5
Space efficient algorithm for solving reachability using tree decomposition and separators	5
Editorial Board	5
Constant amortized time enumeration of Eulerian trails	5
Editorial Board	5
MODRED: A code-based non-interactive key exchange protocol	5
Editorial	5
Combinatorics of minimal absent words for a sliding window	5
Mutual visibility of luminous robots despite angular inaccuracy	5
Approximate distance oracles with improved stretch for sparse graphs	5
Using edge contractions to reduce the semitotal domination number	5
Theoretical design of decentralized auction framework under mobile crowdsourcing environment	5
A certifying and dynamic algorithm for the recognition of proper circular-arc graphs	5
An anomaly-based intrusion detection system using recursive feature elimination technique for improved attack detection	5
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	5
Computational power of autonomous robots: Transparency vs. opaqueness	5
The Convex Set Forming Game	5
Time and energy driven online scheduling problem in EV charging	5
A tight bound for shortest augmenting paths on trees	5
Sign-then-encrypt with security enhancement and compressed ciphertext	5
Location functions for self-stabilizing byzantine tolerant swarms	5
Editorial Board	5
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	5
Editorial	5
Weighted forward looking adaptive coding	5
The equivalence between Galois and Fibonacci NFSRs	5
Refined computational complexities of Hospitals/Residents problem with regional caps	5
Self-similarity of communities of the ABCD model	5
On the complexity of fair coin flipping	5
On finding maximum disjoint paths with different colors: Computational complexity and practical LP-based algorithms	5
Algorithmic aspects of paired disjunctive domination in graphs	5
Editorial Board	5
Model checking differentially private properties	5
Connectivity and constructive algorithms of disjoint paths in dragonfly networks	5
Distributed transformations of Hamiltonian shapes based on line moves	5
The complexity of bicriteria tree-depth	5
Kolmogorov-Loveland betting strategies lose the Betting game on open sets	5
Threshold sampling	5
Editorial Board	5
Better guarantees for k-median with service installation costs	5
Explaining DNA structure	5
Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost	5
Perfectly matched sets in graphs: Parameterized and exact computation	5
Sorting via shuffles with a cut after the longest increasing prefix	5
Editorial Board	5
PSPACE-hardness of variants of the graph coloring game	5
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	5
From multivalued to Boolean functions: Preservation of soft nested canalization	5
Linear-space S-table algorithms for the longest common subsequence problem	5
Remarks on hyperspaces for Priestley spaces	5
On the connectedness of arithmetic hyperplanes	5
Do additional target points speed up evolutionary algorithms?	5
D_PSNI: Delimited persistent stochastic non-interference	5
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	5
The unpaired many-to-many k-disjoint paths in bipartite hypercube-like networks	5
Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints	5
Learning algebraic structures with the help of Borel equivalence relations	5
Partial and constrained level planarity	5
A fault diagnosis method to defend scapegoating attack in network tomography	5
EPTAS for the dual of splittable bin packing with cardinality constraint	4
The Exact Subset MultiCover problem	4
Succinct navigational oracles for families of intersection graphs on a circle	4
Finding geometric representations of apex graphs is NP-hard	4
On the linearity of the periods of subtraction games	4
Parking problem by oblivious mobile robots in infinite grids	4
Optimal 2-traceability codes of length 4	4
Relativized depth	4
Improved algorithms for non-submodular function maximization problem	4
An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth	4
Doubly adaptive zero-knowledge proofs	4
Divide-and-conquer based all spanning tree generation algorithm of a simple connected graph	4