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	45
Closed subsets in Bishop topological groups	38
A new dynamic programming algorithm for the simplified partial digest problem	37
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	35
An algorithm for the secure total domination problem in proper interval graphs	32
CPA/CCA2-secure PKE with squared-exponential DFR from low-noise LPN	30
New (k,l,m)-verifiable multi-secret sharing schemes based on XTR public key system	29
A generalization of a theorem of Rothschild and van Lint	26
Editorial Board	20
Editorial Board	20
Finer-grained reductions in fine-grained hardness of approximation	20
A data structure for substring-substring LCS length queries	19
Editorial Board	18
Editorial Board	18
Improved upper bound for sorting permutations by prefix transpositions	17
Editorial Board	17
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
Complexity issues for timeline-based planning over dense time under future and minimal semantics	16
Editorial Board	16
An algorithmic construction of union-intersection-bounded families	15
Editorial Board	15
Factorisation in the semiring of finite dynamical systems	15
Oracle separations for non-adaptive collapse-free quantum computing	15

Network control games played on graphs	15
Complexity and algorithms for neighbor-sum-2-distinguishing {1,3}-edge-weighting of graphs	14
Editorial Board	14
Integer k-matching preclusion of some interconnection networks	14
Preface	14
On 1-planar graphs with bounded cop-number	14
Towards a general methodology for formal verification on spiking neural P systems	14
Notes on Smyth-completes and local Yoneda-completes	13
Maximal degenerate palindromes with gaps and mismatches	13
On the binary digits of n and n2	13
Sublinear P system solutions to NP-complete problems	13
Physical ZKP protocols for Nurimisaki and Kurodoko	13
Distributed coloring and the local structure of unit-disk graphs	13
Cellular automata and bootstrap percolation	12
Wildcarded identity-based encryption from lattices	12
Call admission problems on grids with advice	12
How real is incomputability in physics?	12
Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation	12
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency	12
The parameterized complexity of welfare guarantees in Schelling segregation	11
A linear time algorithm for connected p-centdian problem on block graphs	11
Three remarks on W graphs	11
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity	11
On the power of threshold-based algorithms for detecting cycles in the CONGEST model	11
A linkable ring signature scheme with unconditional anonymity in the standard model	11
Algorithms for energy conservation in heterogeneous data centers	11
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	11
Deterministic rendezvous in infinite trees	11
Reliability evaluation of complete graph-based recursive networks	11
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	10
On some FPT problems without polynomial Turing compressions	10
Robustly reusable fuzzy extractor from isogeny	10
Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	10
Gacs – Kucera theorem	10
Approximation algorithms for maximum weighted throughput on unrelated machines	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
The computational complexity of forced capture Hnefatafl	10
Editorial Board	10
Updatable searchable symmetric encryption: Definitions and constructions	10
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	10
Identity-based matchmaking encryption with stronger security and instantiation on lattices	10
Powers of low rank sparse matrices	10
Editorial Board	10
Linear Programming complementation	10
On computable numbers, with an application to the Druckproblem	9
Embedding algorithm of spined cube into grid structure and its wirelength computation	9
Complexity of Scorpion Solitaire and applications to Klondike	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
Editorial Board	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
NP-hardness of m-dimensional weighted matching problems	9
Polynomial kernels for paw-free edge modification problems	9
Editorial Board	9
Encoding Boolean networks into reaction systems for investigating causal dependencies in gene regulation	8
Lower bounds for the sum of small-size algebraic branching programs	8
Generating Java code pairing with ChatGPT	8
Grouped domination parameterized by vertex cover, twin cover, and beyond	8
Algebraic properties and transformations of monographs	8
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	8
A substructure based lower bound for eternal vertex cover number	8
Editorial Board	8
On the existence of EFX (and Pareto-optimal) allocations for binary chores	8
Relating randomized right-hand sides to communicating rewriting rules	8
The classes PPA-k: Existence from arguments modulo k	8
Enumeration of subtrees and BC-subtrees with maximum degree no more than k in trees	8
Algorithmic results in secure total dominating sets on graphs	8
Generative abstraction of Markov population processes	8
The existence and efficiency of PMMS allocations	8
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	8
Bisimilarity on Basic Parallel Processes	8
Modelling of DNA mismatch repair with a reversible process calculus	8
On minimal critical exponent of balanced sequences	8
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	8
Near-optimal clustering in the k-machine model	8
The balanced connected subgraph problem for geometric intersection graphs	8
Computational complexity of normalizing constants for the product of determinantal point processes	8
Online coloring of disk graphs	7
Range minimum queries in minimal space	7
Threshold-based network structural dynamics	7
How bad is the merger paradox?	7
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	7
Asynchronous fully-decentralized SGD in the cluster-based model	7
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	7
An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint	7
A categorial approach to reaction systems: First steps	7
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	7
Building bridges – Honoring Nataša Jonoska on the occasion of her 60th birthday	7
Editorial Board	7
Taming the knight's tour: Minimizing turns and crossings	7
Improved algorithms for bandit with graph feedback via regret decomposition	7
Protocols with constant local storage and unreliable communication	7
A categorical model for organic chemistry	7
Disjunctive sums of quasi-nimbers	7
An approximate cost recovery scheme for the k-product facility location game with penalties	7
Eliciting truthful reports with partial signals in repeated games	7
(k,p)-planarity: A relaxation of hybrid planarity	7
The g-component connectivity of graphs	7
Nearly k-universal words – Investigating a part of Simon's congruence	7
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	7
A simple rounding scheme for multistage optimization	7
On a vertex-capturing game	7
Approximation algorithm for prize-collecting sweep cover with base stations	7
Securing data in the cloud using pairing-free inner product functional encryption with unbounded vector size	7
On the complexity of local-equitable coloring of graphs	7
Boundary sketching with asymptotically optimal distance and rotation	7
Cascade products and Wheeler automata	7
Editorial Board	7
Editorial Board	7
Component conditional fault tolerance of hierarchical folded cubic networks	6
Enhancing fault tolerance of balanced hypercube networks by the edge partition method	6
TCS special issue: Combinatorics on Words – WORDS 2021	6
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	6
Languages generated by numerical P systems with thresholds	6
Order based algorithms for the core maintenance problem on edge-weighted graphs	6
On algorithmic applications of sim-width and mim-width of (H1,H2)-free graphs	6
Verifiable Crowd Computing: Coping with bounded rationality	6
Extensional proofs in a propositional logic modulo isomorphisms	6
Multi-stage Proof-of-Works: Properties and vulnerabilities	6
Differential logical relations, part II increments and derivatives	6
Complexity results on register context-free grammars and related formalisms	6
Cutting bamboo down to size	6
Fixed points and attractors of reactantless and inhibitorless reaction systems	6
Editorial Board	6

Editorial Board	6
Editorial Board	6
Exploring the gap between treedepth and vertex cover through vertex integrity	6
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	6
Capacity planning for dependable services	6
Almost envy-freeness for groups: Improved bounds via discrepancy theory	6
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	6
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	6
Mutual witness Gabriel drawings of complete bipartite graphs	6
Editorial Board	6
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	6
In memory of Jérôme Monnot	6
Editorial Board	6
Unified graphical co-modeling, analysis and verification of cyber-physical systems by combining AADL and Simulink/Stateflow	6
Certification of an exact worst-case self-stabilization time	6
Improved unbounded inner-product functional encryption	6
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	6
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	6
A new fast root-finder for black box polynomials	6
Using edge contractions to reduce the semitotal domination number	5
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	5
From multivalued to Boolean functions: Preservation of soft nested canalization	5
Weighted forward looking adaptive coding	5
Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost	5
Editorial Board	5
The complexity of bicriteria tree-depth	5
Editorial	5
The Convex Set Forming Game	5
PSPACE-hardness of variants of the graph coloring game	5
Algorithmic aspects of paired disjunctive domination in graphs	5
Kolmogorov-Loveland betting strategies lose the Betting game on open sets	5
Approximate distance oracles with improved stretch for sparse graphs	5
Distributed transformations of Hamiltonian shapes based on line moves	5
Combinatorics of minimal absent words for a sliding window	5
Remarks on hyperspaces for Priestley spaces	5
Editorial Board	5
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	5
MODRED: A code-based non-interactive key exchange protocol	5
Partial and constrained level planarity	5
D_PSNI: Delimited persistent stochastic non-interference	5
On the power of local graph expansion grammars with and without additional restrictions	5
The unpaired many-to-many k-disjoint paths in bipartite hypercube-like networks	5
Editorial Board	5
Editorial	5
Refined computational complexities of Hospitals/Residents problem with regional caps	5
An anomaly-based intrusion detection system using recursive feature elimination technique for improved attack detection	5
A fault diagnosis method to defend scapegoating attack in network tomography	5
Transactions and contracts based on reaction systems	5
Theoretical design of decentralized auction framework under mobile crowdsourcing environment	5
Optimal L-algorithms for rendezvous of asynchronous mobile robots with extern	5
Editorial Board	5
Editorial Board	5
Editorial Board	5
Do additional target points speed up evolutionary algorithms?	5
Mutual visibility of luminous robots despite angular inaccuracy	5
Sorting via shuffles with a cut after the longest increasing prefix	5
On the connectedness of arithmetic hyperplanes	5
Connectivity and constructive algorithms of disjoint paths in dragonfly networks	5
A certifying and dynamic algorithm for the recognition of proper circular-arc graphs	5
On the complexity of fair coin flipping	5
Location functions for self-stabilizing byzantine tolerant swarms	5
Perfectly matched sets in graphs: Parameterized and exact computation	5
Editorial Board	5
Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints	5
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	5
Constant amortized time enumeration of Eulerian trails	5
Model checking differentially private properties	5
Time and energy driven online scheduling problem in EV charging	5
Computational power of autonomous robots: Transparency vs. opaqueness	5
Self-similarity of communities of the ABCD model	5
Linear-space S-table algorithms for the longest common subsequence problem	5
Learning algebraic structures with the help of Borel equivalence relations	5
On finding maximum disjoint paths with different colors: Computational complexity and practical LP-based algorithms	5
Space efficient algorithm for solving reachability using tree decomposition and separators	5
AbU: A calculus for distributed event-driven programming with attribute-based interaction	4
Chess is hard even for a single player	4
Editorial Board	4
Improved algorithms for non-submodular function maximization problem	4
A new similarity in clustering through users' interest and social relationship	4
A decomposition theorem for number-conserving multi-state cellular automata on triangular grids	4
Revisiting RSA-polynomial problem and semiprime factorization	4
Extremal set theory and LWE based access structure hiding verifiable secret sharing with malicious-majority and free verification	4
The n-trigles, a new variant in the SameSum family	4
A lower bound for constant-size local certification	4
Unpaired set-to-set disjoint path routings in recursive match networks	4
EPTAS for the dual of splittable bin packing with cardinality constraint	4
Feasibility assessments of a dynamical approach to compartmental modelling on graphs: Scaling limits and performance analysis	4
Secret handshakes: Full dynamicity, deniability and lattice-based design	4
For rational numbers with Suppes-Ono division, equational validity is one-one equivalent with Diophantine unsolvability	4
An FPT algorithm for node-disjoint subtrees problems parameterized by treewidth	4
Eccentricity queries and beyond using hub labels	4
Extensional concepts in intensional type theory, revisited	4
Finding geometric representations of apex graphs is NP-hard	4
On the linearity of the periods of subtraction games	4
Space limited linear-time graph algorithms on big data	4