Linear time transformations between combinatorial problems

DOI10.1080/00207168208803302MaRDI QIDQ3936214zbMATH OpenOpenAlexFDO

Authors 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

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Graph theory with applications
• On Isomorphisms and Density of NP and Other Complete Sets
• Satisfiability Is Quasilinear Complete in NQL

Cited in

(11)

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

This page was built for publication: Linear time transformations between combinatorial problems

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3936214)