Linear time transformations between combinatorial problems

DOI10.1080/00207168208803302zbMath0478.68071OpenAlexW2097371553MaRDI QIDQ3936214

A. K. Dewdney

Publication date: 1982

Published in: International Journal of Computer Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1080/00207168208803302

zbMATH Keywords

1-tape transducers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Graph theory (including graph drawing) in computer science (68R10)

Related Items

On unique graph 3-colorability and parsimonious reductions in the plane, On minimum intersection of two minimum dominating sets of interval graphs, Permutation graphs: Connected domination and Steiner trees, On quasilinear-time complexity theory, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, Reducing the generalised Sudoku problem to the Hamiltonian cycle problem, The complexity types of computable sets, Power indices and easier hard problems, Sorting, linear time and the satisfiability problem, Exact complexity of problems of incompletely specified automata

Cites Work

• On Isomorphisms and Density of $NP$ and Other Complete Sets
• Satisfiability Is Quasilinear Complete in NQL
• Unnamed Item
• Unnamed Item