Theoretical Computer Science

Article	Citations
An algorithm for the secure total domination problem in proper interval graphs	54
Finer-grained reductions in fine-grained hardness of approximation	49
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	33
Wildcarded identity-based encryption from lattices	32
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
Preface	22
Editorial Board	22
Editorial Board	22
Factorisation in the semiring of finite dynamical systems	19
Matching cut and variants on bipartite graphs of bounded radius and diameter	19
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	19
Towards a general methodology for formal verification on spiking neural P systems	19
Sublinear P system solutions to NP-complete problems	18
Maximal degenerate palindromes with gaps and mismatches	18
A tighter proof for CCA secure inner product functional encryption: Genericity meets efficiency	17
Notes on Smyth-completes and local Yoneda-completes	16
Axiomatising weak bisimulation congruences over CCS with left merge and communication merge	16
A linkable ring signature scheme with unconditional anonymity in the standard model	16
On 1-planar graphs with bounded cop-number	16
The parameterized complexity of welfare guarantees in Schelling segregation	15
A generalization of a theorem of Rothschild and van Lint	15
Closed subsets in Bishop topological groups	15

On the power of threshold-based algorithms for detecting cycles in the CONGEST model	15
A linear time algorithm for connected p-centdian problem on block graphs	15
A parametric worst-case approach to fairness in cooperative games with transferable utility	15
How real is incomputability in physics?	15
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	15
A new dynamic programming algorithm for the simplified partial digest problem	15
An array P system based on a new variant of pure 2D context-free grammars	14
Reliability evaluation of complete graph-based recursive networks	14
Editorial Board	14
Integer k-matching preclusion of some interconnection networks	13
Editorial Board	13
Improved upper bound for sorting permutations by prefix transpositions	13
Complexity issues for timeline-based planning over dense time under future and minimal semantics	13
New (k,l,m)-verifiable multi-secret sharing schemes based on XTR public key system	13
Call admission problems on grids with advice	13
Editorial Board	12
Complexity and algorithms for neighbor-sum-2-distinguishing {1,3}-edge-weighting of graphs	12
Editorial Board	12
Algorithms for energy conservation in heterogeneous data centers	12
Cellular automata and bootstrap percolation	12
A data structure for substring-substring LCS length queries	12
Editorial Board	12
Editorial Board	12
An optimal algorithm for 2-bounded delay buffer management with lookahead	12
Improvements in the computing efficiency of the probabilities of the LIL test for the PRNG evaluation	12
Three remarks on W graphs	12
The 1-good-neighbour diagnosability of modified bubblesort graphs under the PMC and	11
On the Weisfeiler algorithm of depth-1 stabilization	11
Editorial Board	11
Editorial Board	11
On the binary digits of n and n2	11
Editorial Board	11
A 5k-vertex kernel for 3-path vertex cover	11
On the existence of EFX (and Pareto-optimal) allocations for binary chores	11
Deterministic rendezvous in infinite trees	11
Decreasing verification radius in local certification	11
Linear Programming complementation	11
Robustly reusable fuzzy extractor from isogeny	11
Distributed coloring and the local structure of unit-disk graphs	11
Generating Java code pairing with ChatGPT	10
The computational complexity of forced capture Hnefatafl	10
On the complexity of winner determination and strategic control in conditional approval voting	10
Upper powerdomains of quasicontinuous dcpos	10
Disjoint paths and connected subgraphs for H-free graphs	10
Hypergraph burning, matchings, and zero forcing	10
A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem	10
Computational complexity of normalizing constants for the product of determinantal point processes	10
Grouped domination parameterized by vertex cover, twin cover, and beyond	10
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	10
Approximation algorithms for maximum weighted throughput on unrelated machines	10

Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	10
Powers of low rank sparse matrices	10
On computable numbers, with an application to the Druckproblem	10
Near-optimal clustering in the k-machine model	10
NP-hardness of m-dimensional weighted matching problems	9
New approximation algorithms for RNA secondary structures prediction problems by local search	9
Editorial Board	9
Embedding algorithm of spined cube into grid structure and its wirelength computation	9
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	9
A Myhill-Nerode theorem for register automata and symbolic trace languages	9
Updatable searchable symmetric encryption: Definitions and constructions	9
Algorithmic results in secure total dominating sets on graphs	9
On additive approximate submodularity	9
Generative abstraction of Markov population processes	9
The balanced connected subgraph problem for geometric intersection graphs	9
The impact of core constraints on truthful bidding in combinatorial auctions	9
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	8
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	8
On algorithmic applications of sim-width and mim-width of (H1,H2)-free graphs	8
On some FPT problems without polynomial Turing compressions	8
On minimal critical exponent of balanced sequences	8
Investigation of E-voting system using face recognition using convolutional neural network (CNN)	8
Turing video-based cognitive tests to handle entangled concepts	8
Fixed points and attractors of reactantless and inhibitorless reaction systems	8
Algebraic properties and transformations of monographs	8
Verifiable Crowd Computing: Coping with bounded rationality	8
The existence and efficiency of PMMS allocations	8
Gacs – Kucera theorem	8
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	8
Connectivity and diagnosability of the complete Josephus cube networks under h-extra fault-tolerant model	8
Lower bounds for the sum of small-size algebraic branching programs	8
Cascade products and Wheeler automata	8
Identity-based matchmaking encryption with stronger security and instantiation on lattices	8
Editorial Board	8
On the complexity of nucleolus computation for bipartite b-matching games	8
A categorical model for organic chemistry	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
Certification of an exact worst-case self-stabilization time	7
Mutual witness Gabriel drawings of complete bipartite graphs	7
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	7
On a vertex-capturing game	7
Extensional proofs in a propositional logic modulo isomorphisms	7
Capacity planning for dependable services	7
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	7
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	7
An approximate cost recovery scheme for the k-product facility location game with penalties	7
On the complexity of local-equitable coloring of graphs	7
A simple rounding scheme for multistage optimization	7
Differential logical relations, part II increments and derivatives	7
Bisimilarity on Basic Parallel Processes	7
Eliciting truthful reports with partial signals in repeated games	7
Multi-stage Proof-of-Works: Properties and vulnerabilities	7
Protocols with constant local storage and unreliable communication	7
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	7
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	7
Online coloring of disk graphs	7
Boundary sketching with asymptotically optimal distance and rotation	7
Asynchronous fully-decentralized SGD in the cluster-based model	7
Nearly k-universal words – Investigating a part of Simon's congruence	7
Approximation algorithm for prize-collecting sweep cover with base stations	7
Threshold-based network structural dynamics	7
(k,p)-planarity: A relaxation of hybrid planarity	7
How bad is the merger paradox?	7
Editorial Board	7
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	7
Relating randomized right-hand sides to communicating rewriting rules	6
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	6
Editorial Board	6
On the connectedness of arithmetic hyperplanes	6
An anomaly-based intrusion detection system using recursive feature elimination technique for improved attack detection	6
Partial and constrained level planarity	6
Maximizing the ratio of cluster split to cluster diameter without and with cardinality constraints	6
Sorting via shuffles with a cut after the longest increasing prefix	6
Modelling of DNA mismatch repair with a reversible process calculus	6
Editorial Board	6
Improved unbounded inner-product functional encryption	6
Complexity results on register context-free grammars and related formalisms	6
Order based algorithms for the core maintenance problem on edge-weighted graphs	6
Taming the knight's tour: Minimizing turns and crossings	6

Enhancing fault tolerance of balanced hypercube networks by the edge partition method	6
Exploring the gap between treedepth and vertex cover through vertex integrity	6
Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost	6
#P-hardness proofs of matrix immanants evaluated on restricted matrices	6
Self-similarity of communities of the ABCD model	6
Kolmogorov-Loveland betting strategies lose the Betting game on open sets	6
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	6
Editorial Board	6
Mutual visibility of luminous robots despite angular inaccuracy	6
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	6
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	6
Editorial Board	6
Disjunctive sums of quasi-nimbers	6
Range minimum queries in minimal space	6
A new fast root-finder for black box polynomials	6
MODRED: A code-based non-interactive key exchange protocol	6
Clustering under a knapsack constraint: Parameterized approximation for the knapsack median problem	6
PSPACE-hardness of variants of the graph coloring game	6
Approximate distance oracles with improved stretch for sparse graphs	6
Editorial Board	6
On the power of local graph expansion grammars with and without additional restrictions	6
Cutting bamboo down to size	6
Remarks on hyperspaces for Priestley spaces	6
Almost envy-freeness for groups: Improved bounds via discrepancy theory	6
Unified graphical co-modeling, analysis and verification of cyber-physical systems by combining AADL and Simulink/Stateflow	6
Improved algorithms for bandit with graph feedback via regret decomposition	6
Model checking differentially private properties	5
AbU: A calculus for distributed event-driven programming with attribute-based interaction	5
Subnetwork reliability analysis about complete-transposition graph networks	5
Physical zero-knowledge proof for Ripple Effect	5
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	5
Query answering over inconsistent knowledge bases: A probabilistic approach	5
Space efficient algorithm for solving reachability using tree decomposition and separators	5
The work function algorithm for the paging problem	5
Weighted forward looking adaptive coding	5
Signatures of knowledge for Boolean circuits under standard assumptions	5
Location functions for self-stabilizing byzantine tolerant swarms	5
Optimal L-algorithms for rendezvous of asynchronous mobile robots with extern	5
Combinatorics of minimal absent words for a sliding window	5
Approximating power node-deletion problems	5
Sign-then-encrypt with security enhancement and compressed ciphertext	5
On the complexity of fair coin flipping	5
Constrained flows in networks	5
Computational power of autonomous robots: Transparency vs. opaqueness	5
Polynomial-time checking of generalized Sahlqvist syntactic shape	5
Constant amortized time enumeration of Eulerian trails	5
Editorial Board	5
Distributed transformations of Hamiltonian shapes based on line moves	5
Better guarantees for k-median with service installation costs	5
The Convex Set Forming Game	5
Removing algorithmic discrimination (with minimal individual error)	5
Theoretical design of decentralized auction framework under mobile crowdsourcing environment	5
Query minimization under stochastic uncertainty	5
The complexity of bicriteria tree-depth	5
Repeatedly matching items to agents fairly and efficiently	5
Editorial Board	5
Finitely ambiguous and finitely sequential weighted automata over fields	5
Do additional target points speed up evolutionary algorithms?	5
Intrinsic universality in automata networks III: On symmetry versus asynchrony	5
Editorial Board	5
The non-inclusive diagnosability of a kind of networks	5
Threshold sampling	5
Editorial Board	5
Visibility extension via reflection	5
From multivalued to Boolean functions: Preservation of soft nested canalization	5
Chess is hard even for a single player	5
Algorithmic aspects of paired disjunctive domination in graphs	5
TCS special issue: Combinatorics on Words – WORDS 2021	5
The unpaired many-to-many k-disjoint paths in bipartite hypercube-like networks	5
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	5
A tight bound for shortest augmenting paths on trees	5
A fault diagnosis method to defend scapegoating attack in network tomography	5
Varieties of contextuality based on probability and structural nonembeddability	5
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	5
Editorial Board	5
Time and energy driven online scheduling problem in EV charging	5
Tractability beyond β-acyclicity for conjunctive queries with negation and SAT	5
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	5
An efficient PMC model-based local diagnosis structure and algorithm	5
Refined computational complexities of Hospitals/Residents problem with regional caps	5
The equivalence between Galois and Fibonacci NFSRs	5
Using edge contractions to reduce the semitotal domination number	5
Resource efficient stabilization for local tasks despite unknown capacity links	5
Efficient and reliable post-quantum authentication	5
In memory of Jérôme Monnot	5
On the complexity of distance-d independent set reconfiguration	5
Languages generated by numerical P systems with thresholds	5
Revisiting RSA-polynomial problem and semiprime factorization	5
Learning algebraic structures with the help of Borel equivalence relations	5
Linear-space S-table algorithms for the longest common subsequence problem	5
Connectivity and constructive algorithms of disjoint paths in dragonfly networks	5
Relativized depth	4
Optimal 2-traceability codes of length 4	4
On the linearity of the periods of subtraction games	4
Finding geometric representations of apex graphs is NP-hard	4