Computing on binary strings

DOI10.1016/j.tcs.2014.09.039zbMath1303.68162arXiv1112.0278OpenAlexW2015718462MaRDI QIDQ476852

Tian-Ming Bu, Chen Yuan, Peng Zhang

Publication date: 2 December 2014

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1112.0278

zbMATH Keywords

NP-hardcombinatorial algorithmbinary stringsBoolean operation\(\#\)P-complete

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Algorithms on strings (68W32)

Related Items

Constant factor approximation for the weighted partial degree bounded edge packing problem ⋮ Constant Factor Approximation for the Weighted Partial Degree Bounded Edge Packing Problem

Cites Work

• The Complexity of Counting Cuts and of Computing the Probability that a Graph is Connected
• A threshold of ln n for approximating set cover
• Reducibility among Combinatorial Problems
• The Theory of Representation for Boolean Algebras
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Computing on binary strings