Theoretical Computer Science

Article	Citations
An algorithm for the secure total domination problem in proper interval graphs	56
Finer-grained reductions in fine-grained hardness of approximation	51
Network control games played on graphs	44
An algorithmic construction of union-intersection-bounded families	37
Oracle separations for non-adaptive collapse-free quantum computing	34
Wildcarded identity-based encryption from lattices	25
Editorial Board	23
Physical ZKP protocols for Nurimisaki and Kurodoko	23
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity	23
Editorial Board	22
Preface	20
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	19
Factorisation in the semiring of finite dynamical systems	19
Sublinear P system solutions to NP-complete problems	19
Towards a general methodology for formal verification on spiking neural P systems	19
Maximal degenerate palindromes with gaps and mismatches	19
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency	18
Notes on Smyth-completes and local Yoneda-completes	17
Matching cut and variants on bipartite graphs of bounded radius and diameter	17
A linkable ring signature scheme with unconditional anonymity in the standard model	17
Axiomatising weak bisimulation congruences over CCS with left merge and communication merge	16
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	16
On the power of threshold-based algorithms for detecting cycles in the CONGEST model	16
On 1-planar graphs with bounded cop-number	16
How real is incomputability in physics?	16

A parametric worst-case approach to fairness in cooperative games with transferable utility	15
A linear time algorithm for connected p-centdian problem on block graphs	15
A generalization of a theorem of Rothschild and van Lint	15
Closed subsets in Bishop topological groups	15
Integer k-matching preclusion of some interconnection networks	14
A new dynamic programming algorithm for the simplified partial digest problem	14
New (k,l,m)-verifiable multi-secret sharing schemes based on XTR public key system	14
Editorial Board	14
Editorial Board	14
Editorial Board	13
Call admission problems on grids with advice	13
Editorial Board	13
Complexity issues for timeline-based planning over dense time under future and minimal semantics	13
The 1-good-neighbour diagnosability of modified bubblesort graphs under the PMC and	12
Three remarks on W graphs	12
Complexity and algorithms for neighbor-sum-2-distinguishing {1,3}-edge-weighting of graphs	12
On the binary digits of n and n2	12
Editorial Board	12
Editorial Board	12
A data structure for substring-substring LCS length queries	12
Editorial Board	12
Deterministic rendezvous in infinite trees	12
Distributed coloring and the local structure of unit-disk graphs	12
Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation	12
Cellular automata and bootstrap percolation	12
Decreasing verification radius in local certification	12
Linear Programming complementation	11
The parameterized complexity of welfare guarantees in Schelling segregation	11
Editorial Board	11
Robustly reusable fuzzy extractor from isogeny	11
Turing video-based cognitive tests to handle entangled concepts	11
On the Weisfeiler algorithm of depth-1 stabilization	11
An array P system based on a new variant of pure 2D context-free grammars	11
On the existence of EFX (and Pareto-optimal) allocations for binary chores	11
Editorial Board	11
A 5k-vertex kernel for 3-path vertex cover	11
Reliability evaluation of complete graph-based recursive networks	11
On some FPT problems without polynomial Turing compressions	11
Approximation algorithms for maximum weighted throughput on unrelated machines	11
Powers of low rank sparse matrices	10
Upper powerdomains of quasicontinuous dcpos	10
New approximation algorithms for RNA secondary structures prediction problems by local search	10
The computational complexity of forced capture Hnefatafl	10
On the complexity of winner determination and strategic control in conditional approval voting	10
Computational complexity of normalizing constants for the product of determinantal point processes	10
Updatable searchable symmetric encryption: Definitions and constructions	10
Grouped domination parameterized by vertex cover, twin cover, and beyond	10
A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem	10
On the complexity of nucleolus computation for bipartite b-matching games	10
Generative abstraction of Markov population processes	10

On computable numbers, with an application to the Druckproblem	10
Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	10
The impact of core constraints on truthful bidding in combinatorial auctions	9
The balanced connected subgraph problem for geometric intersection graphs	9
On additive approximate submodularity	9
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	9
Investigation of E-voting system using face recognition using convolutional neural network (CNN)	9
Near-optimal clustering in the k-machine model	9
Editorial Board	9
NP-hardness of m-dimensional weighted matching problems	9
A Myhill-Nerode theorem for register automata and symbolic trace languages	9
On minimal critical exponent of balanced sequences	9
Editorial Board	9
Gacs – Kucera theorem	9
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	9
Algorithmic results in secure total dominating sets on graphs	9
The existence and efficiency of PMMS allocations	9
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	8
Disjoint paths and connected subgraphs for H-free graphs	8
Editorial Board	8
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	8
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	8
Generating Java code pairing with ChatGPT	8
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	8
Identity-based matchmaking encryption with stronger security and instantiation on lattices	8
Lower bounds for the sum of small-size algebraic branching programs	8
Relating randomized right-hand sides to communicating rewriting rules	8
Taming the knight's tour: Minimizing turns and crossings	8
Connectivity and diagnosability of the complete Josephus cube networks under h-extra fault-tolerant model	8
Hypergraph burning, matchings, and zero forcing	8
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	8
Embedding algorithm of spined cube into grid structure and its wirelength computation	8
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	8
Range minimum queries in minimal space	8
Algebraic properties and transformations of monographs	8
Subtyping context-free session types	8
Editorial Board	7
Almost envy-freeness for groups: Improved bounds via discrepancy theory	7
Mutual witness Gabriel drawings of complete bipartite graphs	7
Eliciting truthful reports with partial signals in repeated games	7
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	7
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	7
A categorical model for organic chemistry	7
Boundary sketching with asymptotically optimal distance and rotation	7
Cascade products and Wheeler automata	7
Bisimilarity on Basic Parallel Processes	7
An approximate cost recovery scheme for the k-product facility location game with penalties	7
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	7
A simple rounding scheme for multistage optimization	7
Certification of an exact worst-case self-stabilization time	7
On the complexity of local-equitable coloring of graphs	7
Improved algorithms for bandit with graph feedback via regret decomposition	7
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	7
Improved unbounded inner-product functional encryption	7
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	7
Online coloring of disk graphs	7
An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint	7
Cutting bamboo down to size	7
Nearly k-universal words – Investigating a part of Simon's congruence	7
Protocols with constant local storage and unreliable communication	7
How bad is the merger paradox?	7
Approximation algorithm for prize-collecting sweep cover with base stations	7
Complexity results on register context-free grammars and related formalisms	7
Extensional proofs in a propositional logic modulo isomorphisms	7
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	7
Multi-stage Proof-of-Works: Properties and vulnerabilities	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
Asynchronous fully-decentralized SGD in the cluster-based model	7
Capacity planning for dependable services	7
Threshold-based network structural dynamics	7
On a vertex-capturing game	7
Unified graphical co-modeling, analysis and verification of cyber-physical systems by combining AADL and Simulink/Stateflow	6
On the power of local graph expansion grammars with and without additional restrictions	6
Mutual visibility of luminous robots despite angular inaccuracy	6
Enhancing fault tolerance of balanced hypercube networks by the edge partition method	6
Using edge contractions to reduce the semitotal domination number	6
Editorial Board	6
Linear-space S-table algorithms for the longest common subsequence problem	6
Space efficient algorithm for solving reachability using tree decomposition and separators	6

Weighted forward looking adaptive coding	6
Remarks on hyperspaces for Priestley spaces	6
Editorial Board	6
Exploring the gap between treedepth and vertex cover through vertex integrity	6
Fixed points and attractors of reactantless and inhibitorless reaction systems	6
Modelling of DNA mismatch repair with a reversible process calculus	6
Editorial Board	6
MODRED: A code-based non-interactive key exchange protocol	6
Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost	6
Verifiable Crowd Computing: Coping with bounded rationality	6
Constant amortized time enumeration of Eulerian trails	6
TCS special issue: Combinatorics on Words – WORDS 2021	6
Partial and constrained level planarity	6
Kolmogorov-Loveland betting strategies lose the Betting game on open sets	6
Editorial Board	6
Renaming in distributed certification	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
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	6
Sorting via shuffles with a cut after the longest increasing prefix	6
On the connectedness of arithmetic hyperplanes	6
Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints	6
The complexity of bicriteria tree-depth	6
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	6
Approximate distance oracles with improved stretch for sparse graphs	6
Algorithmic aspects of paired disjunctive domination in graphs	6
Disjunctive sums of quasi-nimbers	6
Intrinsic universality in automata networks III: On symmetry versus asynchrony	5
Location functions for self-stabilizing byzantine tolerant swarms	5
An efficient PMC model-based local diagnosis structure and algorithm	5
Clustering under a knapsack constraint: Parameterized approximation for the knapsack median problem	5
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	5
Threshold sampling	5
PSPACE-hardness of variants of the graph coloring game	5
Linear-time computation of DAWGs, symmetric indexing structures, and MAWs for integer alphabets	5
An anomaly-based intrusion detection system using recursive feature elimination technique for improved attack detection	5
Feasibility assessments of a dynamical approach to compartmental modelling on graphs: Scaling limits and performance analysis	5
The unpaired many-to-many k-disjoint paths in bipartite hypercube-like networks	5
AbU: A calculus for distributed event-driven programming with attribute-based interaction	5
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	5
Signatures of knowledge for Boolean circuits under standard assumptions	5
Model checking differentially private properties	5
Repeatedly matching items to agents fairly and efficiently	5
A fault diagnosis method to defend scapegoating attack in network tomography	5
Tractability beyond β-acyclicity for conjunctive queries with negation and SAT	5
On the complexity of distance-d independent set reconfiguration	5
Editorial Board	5
Polynomial-time checking of generalized Sahlqvist syntactic shape	5
Editorial Board	5
An operational quantum information framework for experimental studies on color perception	5
Editorial Board	5
Finitely ambiguous and finitely sequential weighted automata over fields	5
Sign-then-encrypt with security enhancement and compressed ciphertext	5
Learning algebraic structures with the help of Borel equivalence relations	5
Approximating power node-deletion problems	5
Connectivity and constructive algorithms of disjoint paths in dragonfly networks	5
Fast computations on ordered nominal sets	5
Computational power of autonomous robots: Transparency vs. opaqueness	5
Editorial Board	5
The Convex Set Forming Game	5
Removing algorithmic discrimination (with minimal individual error)	5
Do additional target points speed up evolutionary algorithms?	5
Editorial Board	5
Time and energy driven online scheduling problem in EV charging	5
Better guarantees for k-median with service installation costs	5
Combinatorics of minimal absent words for a sliding window	5
Efficient and reliable post-quantum authentication	5
Chess is hard even for a single player	5
From multivalued to Boolean functions: Preservation of soft nested canalization	5
Constrained flows in networks	5
Refined computational complexities of Hospitals/Residents problem with regional caps	5
The equivalence between Galois and Fibonacci NFSRs	5
Resource efficient stabilization for local tasks despite unknown capacity links	5
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	5
On the complexity of fair coin flipping	5
Self-similarity of communities of the ABCD model	5
A decomposition theorem for number-conserving multi-state cellular automata on triangular grids	5
Optimal L-algorithms for rendezvous of asynchronous mobile robots with extern	5
Perfectly matched sets in graphs: Parameterized and exact computation	5
Theoretical design of decentralized auction framework under mobile crowdsourcing environment	5
A tight bound for shortest augmenting paths on trees	5
Distributed transformations of Hamiltonian shapes based on line moves	5
Varieties of contextuality based on probability and structural nonembeddability	5
In memory of Jérôme Monnot	5
Query answering over inconsistent knowledge bases: A probabilistic approach	5
Subnetwork reliability analysis about complete-transposition graph networks	5
The work function algorithm for the paging problem	5
Visibility extension via reflection	5
Editorial Board	5
Revisiting RSA-polynomial problem and semiprime factorization	5
Languages generated by numerical P systems with thresholds	5
Efficient computation of arbitrary control dependencies	4
A lower bound for constant-size local certification	4
Quantum circuits with classical channels and the principle of deferred measurements	4
Several methods of analysis for cardinality constrained bin packing	4