Linear time transformations between combinatorial problems
From MaRDI portal
Publication:3936214
DOI10.1080/00207168208803302zbMath0478.68071MaRDI QIDQ3936214
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
68Q25: Analysis of algorithms and problem complexity
68Q45: Formal languages and automata
68R10: Graph theory (including graph drawing) in computer science
Related Items
Power indices and easier hard problems, On unique graph 3-colorability and parsimonious reductions in the plane, On quasilinear-time complexity theory, The class of problems that are linearly equivalent to Satisfiability or a uniform method for proving NP-completeness, Permutation graphs: Connected domination and Steiner trees, The complexity types of computable sets, On minimum intersection of two minimum dominating sets of interval graphs, Sorting, linear time and the satisfiability problem, Exact complexity of problems of incompletely specified automata
Cites Work