Theoretical Computer Science

Article	Citations
An algorithm for the secure total domination problem in proper interval graphs	66
Finer-grained reductions in fine-grained hardness of approximation	54
An algorithmic construction of union-intersection-bounded families	51
Maximal degenerate palindromes with gaps and mismatches	39
Oracle separations for non-adaptive collapse-free quantum computing	39
Sublinear P system solutions to NP-complete problems	38
A linkable ring signature scheme with unconditional anonymity in the standard model	32
Matching cut and variants on bipartite graphs of bounded radius and diameter	30
On CNF formulas irredundant with respect to unit clause propagation	29
How real is incomputability in physics?	25
Editorial Board	24
Preface	24
Editorial Board	24
Parameterised approximation of the fixation probability of the dominant mutation in the multi-type Moran process	23
The 1-good-neighbour diagnosability of modified bubblesort graphs under the PMC and	20
Editorial Board	20
On the power of threshold-based algorithms for detecting cycles in the CONGEST model	19
The parameterized complexity of welfare guarantees in Schelling segregation	19
Axiomatising weak bisimulation congruences over CCS with left merge and communication merge	19
On 1-planar graphs with bounded cop-number	19
A linear time algorithm for connected p-centdian problem on block graphs	18
A generalization of a theorem of Rothschild and van Lint	17
A parametric worst-case approach to fairness in cooperative games with transferable utility	17
Editorial Board	17
Closed subsets in Bishop topological groups	17

A new dynamic programming algorithm for the simplified partial digest problem	17
Editorial Board	16
Integer k-matching preclusion of some interconnection networks	16
Editorial Board	15
Editorial Board	15
Cellular automata and bootstrap percolation	15
Editorial Board	15
Reliability evaluation of complete graph-based recursive networks	14
Network control games played on graphs	14
Editorial Board	14
On the binary digits of n and n2	14
Towards a general methodology for formal verification on spiking neural P systems	14
Distributed coloring and the local structure of unit-disk graphs	14
An array P system based on a new variant of pure 2D context-free grammars	13
A 5k-vertex kernel for 3-path vertex cover	13
Deterministic rendezvous in infinite trees	13
Notes on Smyth-completes and local Yoneda-completes	13
Decreasing verification radius in local certification	13
When does FTP become FPT?	13
Factorisation in the semiring of finite dynamical systems	13
Dynamic debt swapping in financial networks	13
Three remarks on W2 graphs	13
Partial key exposure attacks on Prime Power RSA with non-consecutive blocks	12
Reliability measure of the n-th cartesian product of complete graph K4 on h-extra edge-connectivity	12
Investigation of E-voting system using face recognition using convolutional neural network (CNN)	12
On the existence of EFX (and Pareto-optimal) allocations for binary chores	12
Physical ZKP protocols for Nurimisaki and Kurodoko	12
On the Weisfeiler algorithm of depth-1 stabilization	12
Linear Programming complementation	12
Editorial Board	12
Generating Java code pairing with ChatGPT	12
The g-good-neighbor diagnosability of lexicographic product networks under the PMC model	12
Weakly leveled planarity with bounded span	12
Editorial Board	12
Approximation algorithms for maximum weighted throughput on unrelated machines	12
Hypergraph burning, matchings, and zero forcing	11
Powers of low rank sparse matrices	11
A strongly polynomial time approximation algorithm for the min-max clustered cycle cover problem	11
Identity-based matchmaking encryption with stronger security and instantiation on lattices	11
On the complexity of winner determination and strategic control in conditional approval voting	11
Dormancy-aware timed branching bisimilarity with an application to communication protocol analysis	11
The computational complexity of forced capture Hnefatafl	11
On the detection of local and global amoebas: Theoretical insights and practical algorithms	11
On the complexity of nucleolus computation for bipartite b-matching games	10
New approximation algorithms for RNA secondary structures prediction problems by local search	10
Gacs – Kucera theorem	10
On additive approximate submodularity	10
On minimal critical exponent of balanced sequences	10
Computational complexity of normalizing constants for the product of determinantal point processes	10
Updatable searchable symmetric encryption: Definitions and constructions	10

The balanced connected subgraph problem for geometric intersection graphs	10
The impact of core constraints on truthful bidding in combinatorial auctions	10
On approximability of propositional model counting	10
Generative abstraction of Markov population processes	10
Editorial Board	10
Editorial Board	10
Subtyping context-free session types	9
Complexity and approximation algorithms for two parallel dedicated machine scheduling with conflict constraints	9
Upper powerdomains of quasicontinuous dcpos	9
Analysis of key reuse security for Aigis.KEM	9
Fast and simple (1 + ε)Δ-edge-coloring of dense graphs	9
Connectivity and diagnosability of the complete Josephus cube networks under h-extra fault-tolerant model	9
NP-hardness of m-dimensional weighted matching problems	9
Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and k-system constraints	9
A weak inverse of language neighborhoods and its properties	9
Single- and multi-objective evolutionary algorithms for the knapsack problem with dynamically changing constraints	9
Editorial Board	9
Hierarchical decompositions of implicational bases for the enumeration of meet-irreducible elements	9
The existence and efficiency of PMMS allocations	9
Turing video-based cognitive tests to handle entangled concepts	9
Robustly reusable fuzzy extractor from isogeny	9
On the order of lazy cellular automata	9
Verifiable Crowd Computing: Coping with bounded rationality	8
Cascade products and Wheeler automata	8
A categorical model for organic chemistry	8
Parallel Contextual Array Insertion Deletion Grammars, Pure 2D Context-Free Grammars and Associated P Systems	8
Capacity planning for dependable services	8
Grouped domination parameterized by vertex cover, twin cover, and beyond	8
Algebraic properties and transformations of monographs	8
Order based algorithms for the core maintenance problem on edge-weighted graphs	8
Online coloring of disk graphs	8
Securing data in the cloud using pairing-free inner product functional encryption with unbounded vector size	8
Optimization on the smallest eigenvalue of grounded Laplacian matrix via edge addition	8
Asynchronous fully-decentralized SGD in the cluster-based model	8
On computable numbers, with an application to the Druckproblem	8
A categorical approach to reversible Turing machines and Brin-Thompson groups	8
Lower bounds for the sum of small-size algebraic branching programs	8
(Definitely not) Boring interaction abstract machines	8
An approximate cost recovery scheme for the k-product facility location game with penalties	8
Decision algorithms for reversibility of 1D cellular automata under reflective boundary conditions	8
Editorial Board	8
Fixed points and attractors of reactantless and inhibitorless reaction systems	8
On properties of languages accepted by deterministic pushdown automata with translucent input letters	8
Eliciting truthful reports with partial signals in repeated games	7
How bad is the merger paradox?	7
Extensional proofs in a propositional logic modulo isomorphisms	7
Streaming approximation scheme for minimizing total completion time on parallel machines subject to varying processing capacity	7
A new fast root-finder for black box polynomials	7
Diagonal of pseudoinverse of graph Laplacian: Fast estimation and exact results	7
Process-commutative distributed objects: From cryptocurrencies to Byzantine-Fault-Tolerant CRDTs	7
Greedy+Singleton: An efficient approximation algorithm for k-submodular knapsack maximization	7
Renaming in distributed certification	7
Improved algorithms for bandit with graph feedback via regret decomposition	7
Mutual witness Gabriel drawings of complete bipartite graphs	7
Protocols with constant local storage and unreliable communication	7
Certification of an exact worst-case self-stabilization time	7
Almost envy-freeness for groups: Improved bounds via discrepancy theory	7
Nearly k-universal words – Investigating a part of Simon's congruence	7
Enhancing fault tolerance of balanced hypercube networks by the edge partition method	7
Modelling of DNA mismatch repair with a reversible process calculus	7
Editorial Board	7
Self-stabilizing spanner topology control solutions in wireless ad hoc networks	7
Threshold-based network structural dynamics	7
Multi-stage Proof-of-Works: Properties and vulnerabilities	7
Complexity results on register context-free grammars and related formalisms	7
Relating randomized right-hand sides to communicating rewriting rules	7
Quantum collision search for ternary LWE keys	7
On algorithmic applications of sim-width and mim-width of (H1,H2)-free graphs	7
On a vertex-capturing game	7
Improved unbounded inner-product functional encryption	7
Editorial Board	7
On the connectedness of arithmetic hyperplanes	6
Boundary sketching with asymptotically optimal distance and rotation	6
Approximate distance oracles with improved stretch for sparse graphs	6
Connectivity and constructive algorithms of disjoint paths in dragonfly networks	6
Constant amortized time enumeration of Eulerian trails	6
A fault diagnosis method to defend scapegoating attack in network tomography	6
Preface for the special issue of Theoretical Computer Science in honor of the 60th birthday of Yuxi Fu	6
Editorial Board	6
Languages generated by numerical P systems with thresholds	6

Location functions for self-stabilizing byzantine tolerant swarms	6
On the power of local graph expansion grammars with and without additional restrictions	6
Using edge contractions to reduce the semitotal domination number	6
Dirac-type condition for rainbow chorded pancyclicity	6
In memory of Jérôme Monnot	6
Editorial Board	6
An accelerated deterministic algorithm for maximizing monotone submodular minus modular function with cardinality constraint	6
MODRED: A code-based non-interactive key exchange protocol	6
From multivalued to Boolean functions: Preservation of soft nested canalization	6
Space efficient algorithm for solving reachability using tree decomposition and separators	6
Remarks on hyperspaces for Priestley spaces	6
Editorial Board	6
Do additional target points speed up evolutionary algorithms?	6
Sorting via shuffles with a cut after the longest increasing prefix	6
Editorial Board	6
#P-Hardness proofs of matrix immanants evaluated on restricted matrices	6
Combinatorics of minimal absent words for a sliding window	6
Refined computational complexities of Hospitals/Residents problem with regional caps	6
Computational task offloading algorithm based on deep reinforcement learning and multi-task dependency	6
Approximation algorithm for prize-collecting sweep cover with base stations	6
Disjunctive sums of quasi-nimbers	6
Partial and constrained level planarity	6
Efficiency and inefficiency of Nash equilibrium for scheduling games on batching-machines with activation cost	6
Algorithmic aspects of paired disjunctive domination in graphs	6
Kolmogorov-Loveland betting strategies lose the Betting game on open sets	6
Support preorder on finitely supported Cb	6
The complexity of bicriteria tree-depth	6
Undecidability of the universal support problem for weighted automata over zero-sum-free commutative semirings	6
Editorial Board	6
Editorial Board	6
Editorial Board	6
The non-inclusive diagnosability of a kind of networks	5
Editorial Board	5
Learning algebraic structures with the help of Borel equivalence relations	5
Query answering over inconsistent knowledge bases: A probabilistic approach	5
Decision problems on geometric tilings	5
Weighted forward looking adaptive coding	5
Chess is hard even for a single player	5
Subnetwork reliability analysis about complete-transposition graph networks	5
A cornering strategy for synchronizing a DFA	5
Distributed transformations of Hamiltonian shapes based on line moves	5
Optimal L-algorithms for rendezvous of asynchronous mobile robots with extern	5
On the complexity of distance-d independent set reconfiguration	5
Searching in trees with monotonic query times	5
The Voting algorithm is robust to various noise models	5
Less is more revisited: Association with global protocols and multiparty sessions	5
Decision on block size in blockchain systems by evolutionary equilibrium analysis	5
Pebble Guided Rendezvous Despite Fault	5
Perfectly matched sets in graphs: Parameterized and exact computation	5
Sign-then-encrypt with security enhancement and compressed ciphertext	5
Removing algorithmic discrimination (with minimal individual error)	5
Self-similarity of communities of the ABCD model	5
Editorial	5
The Convex Set Forming Game	5
Constrained flows in networks	5
An operational quantum information framework for experimental studies on color perception	5
Theoretical design of decentralized auction framework under mobile crowdsourcing environment	5
The equivalence between Galois and Fibonacci NFSRs	5
Model checking differentially private properties	5
Polynomial-time checking of generalized Sahlqvist syntactic shape	5
Linear-space S-table algorithms for the longest common subsequence problem	5
Efficient and reliable post-quantum authentication	5
An anomaly-based intrusion detection system using recursive feature elimination technique for improved attack detection	5
A Java-like calculus with heterogeneous coeffects	5
Covering and partitioning of split, chain and cographs with isometric paths	5
Visibility extension via reflection	5
TCS special issue: Combinatorics on Words – WORDS 2021	5
A decomposition theorem for number-conserving multi-state cellular automata on triangular grids	5
Resource efficient stabilization for local tasks despite unknown capacity links	5
Feasibility assessments of a dynamical approach to compartmental modelling on graphs: Scaling limits and performance analysis	5
Mutual visibility of luminous robots despite angular inaccuracy	5
Varieties of contextuality based on probability and structural nonembeddability	5
On the traceability of group signatures: Uncorrupted user must exist	5
Stand up indulgent gathering	5
How majority-vote crossover and estimation-of-distribution algorithms cope with fitness valleys	5
Revisiting RSA-polynomial problem and semiprime factorization	5
Move-optimal arbitrary pattern formation by mobile robots on rectangular grid using near-optimal spatial area	5
Corrigendum to “Complexity and approximability of the happy set problem” [Theor. Comput. Sci. 866 (2021) 123–144]	5
Hamiltonicity parameterized by mim-width is (indeed) para-NP-hard	5
Centralised connectivity-preserving transformations for programmable matter: A minimal seed approach	5
A logarithmic-sized accountable ring signature scheme in the standard model	5
Approximating power node-deletion problems	5
Integer-valued martingales and cl-Turing reductions	5
Clustering under a knapsack constraint: Parameterized approximation for the knapsack median problem	5
Editorial Board	5
LL(k) cooperating distributed grammar systems	5
Space limited linear-time graph algorithms on big data	5
Computational power of autonomous robots: Transparency vs. opaqueness	5
Fast computations on ordered nominal sets	5
Time and energy driven online scheduling problem in EV charging	5
Better guarantees for k-median with service installation costs	5
Efficient computation of arbitrary control dependencies	4
A characterisation of P by DLOGTIME-uniform families of polarizationless P systems using only dissolution rules	4
Drawing graphs with k	4
Approximation algorithms for facility location and k-median with differential privacy	4