Copertina

DNA Probe Computing System for Solving NP-Complete Problems

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Xu, Jin, Shi, XiaoLong, Chen, Xin, Wang, Fang, Li, Sirui, Ye, Pali, Zhang, Boliang, Deng, Di, Kou, Zheng, Qiang, Xiaoli
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Algorithmic Reductions: Network Flow and NP-Completeness in Real-World Scheduling Problems
di: Sinhal, Anay, et al.
Pubblicazione: (2026)

An Invitation to "Fine-grained Complexity of NP-Complete Problems"
di: Nederlof, Jesper
Pubblicazione: (2026)

NP-Completeness for the Space-Optimality of Double-Array Tries
di: Bannai, Hideo, et al.
Pubblicazione: (2024)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
di: Bampis, Evripidis, et al.
Pubblicazione: (2025)

An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
di: Murakami, Hitoshi, et al.
Pubblicazione: (2024)

Recognizing Sumsets is NP-Complete
di: Abboud, Amir, et al.
Pubblicazione: (2024)

Parsimonious Learning-Augmented Approximations for Dense Instances of $\mathcal{NP}$-hard Problems
di: Bampis, Evripidis, et al.
Pubblicazione: (2024)

NP-Hardness and a PTAS for the Pinwheel Problem
di: Kleinberg, Robert, et al.
Pubblicazione: (2026)

Approximating Unrelated Machine Weighted Completion Time Using Iterative Rounding and Computer Assisted Proofs
di: Li, Shi
Pubblicazione: (2024)

Tokenisation is NP-Complete
di: Whittington, Philip, et al.
Pubblicazione: (2024)

A Partition-and-Merge Algorithm for Solving the Steiner Tree Problem in Large Graphs
di: Sun, Ming, et al.
Pubblicazione: (2022)

A Polynomial-Time Deterministic Algorithm for an NP-Complete Problem
di: Jiang, Xinwen, et al.
Pubblicazione: (2021)

NP-Completeness of Deterministic Communication Complexity via Relaxed Interlacing
di: Gaspers, Serge, et al.
Pubblicazione: (2025)

NP-hardness and a PTAS for the Euclidean Steiner Line Problem
di: Bartlmae, Simon, et al.
Pubblicazione: (2024)

Temporal Routing in Static Networks: The Schedule Completion Problem
di: Döring, Michelle, et al.
Pubblicazione: (2026)

From Data Completion to Problems on Hypercubes: A Parameterized Analysis of the Independent Set Problem
di: Eiben, Eduard, et al.
Pubblicazione: (2024)

Structural Optimal Jacobian Accumulation and Minimum Edge Count are NP-Complete Under Vertex Elimination
di: Bentert, Matthias, et al.
Pubblicazione: (2025)

On Differential Privacy for Adaptively Solving Search Problems via Sketching
di: Feng, Shiyuan, et al.
Pubblicazione: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
di: Guruswami, Venkatesan, et al.
Pubblicazione: (2023)

NP-Completeness of the Combinatorial Distance Matrix Realisation Problem
di: Fairbairn, David L., et al.
Pubblicazione: (2024)

Approximation Algorithms for Packing Cycles and Paths in Complete Graphs
di: Zhao, Jingyang, et al.
Pubblicazione: (2023)

Computational-Statistical Tradeoffs from NP-hardness
di: Blanc, Guy, et al.
Pubblicazione: (2025)

Computational Complexity of the Interval Ordering Problem
di: Pawlowski, Simeon, et al.
Pubblicazione: (2026)

Solving the Multiobjective Quasi-Clique Problem
di: Santos, Daniela Scherer dos, et al.
Pubblicazione: (2024)

A Fixed Parameter Tractable Approach for Solving the Vertex Cover Problem in Polynomial Time Complexity
di: Tayal, Mumuksh
Pubblicazione: (2025)

Turing Completeness of GNU find: From mkdir-assisted Loops to Standalone Computation
di: Oka, Keigo
Pubblicazione: (2026)

Solving Co-Path/Cycle Packing and Co-Path Packing Faster Than $3^k$
di: Liu, Yuxi, et al.
Pubblicazione: (2024)

Minimizing the Number of Tardy Jobs and Maximal Tardiness on a Single Machine is NP-hard
di: Heeger, Klaus, et al.
Pubblicazione: (2024)

Solving NP-hard Problems on \textsc{GaTEx} Graphs: Linear-Time Algorithms for Perfect Orderings, Cliques, Colorings, and Independent Sets
di: Hellmuth, Marc, et al.
Pubblicazione: (2023)

The APX-hardness of the Traveling Tournament Problem
di: Zhao, Jingyang, et al.
Pubblicazione: (2023)

Solving the Correlation Cluster LP in Sublinear Time
di: Cao, Nairen, et al.
Pubblicazione: (2025)

Solving the Probabilistic Profitable Tour Problem on a Tree
di: Angelelli, Enrico, et al.
Pubblicazione: (2022)

Min-1-Planarity is NP-Hard
di: Okada, Yuto
Pubblicazione: (2026)

Improved Approximations for Dial-a-Ride Problems
di: Zhao, Jingyang, et al.
Pubblicazione: (2026)

An Improved Approximation Algorithm for the Capacitated Arc Routing Problem
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Improved Approximations for the Unsplittable Capacitated Vehicle Routing Problem
di: Zhao, Jingyang, et al.
Pubblicazione: (2026)

Fine-Grained Computation in 3-Space: Matrix Multiplication and Graph Problems
di: Stout, Quentin F.
Pubblicazione: (2024)

Approximation Algorithms for the Cumulative Vehicle Routing Problem with Stochastic Demands
di: Zhao, Jingyang, et al.
Pubblicazione: (2025)

Compressed Game Solving
di: Considine, Jeffrey
Pubblicazione: (2024)

The Online Submodular Assignment Problem
di: Hathcock, Daniel, et al.
Pubblicazione: (2024)