Parameterized-NL Completeness of Combinatorial Problems by Short Logarithmic-Space Reductions and Immediate Consequences of the Linear Space Hypothesis.
Tomoyuki YamakamiPublished in: FTC (1) (2022)
Keyphrases
- linear space
- combinatorial problems
- constraint programming
- space efficient
- combinatorial optimization
- constraint satisfaction problems
- phase transition
- external memory
- metaheuristic
- traveling salesman problem
- nearest neighbor search
- constraint satisfaction
- arbitrary shape
- locality sensitive hashing
- global constraints
- branch and bound algorithm
- data streams
- junction tree
- multi dimensional