Feasible graphs with standard universe

DOI10.1016/S0168-0072(97)00064-XMaRDI QIDQ1295403zbMATH OpenOpenAlexFDO

Authors Douglas Cenzer, Jeffrey Remmel

Publication date 14 June 2000

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/s0168-0072(97)00064-x

zbMATH Keywords

isomorphism problemrecursive treerecursive isomorphismcomputable treesrecursive graphsp-time modelsrecursive equivalence relation

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Computable structure theory, computable model theory (03C57) Theory of numerations, effectively presented structures (03D45) Complexity of computation (including implicit computational complexity) (03D15)

Recommendations

• Some universal graphs
• Almost universal graphs
• Edge-realizable graphs with universal vertices
• Universal and unavoidable graphs
• Realizability of graphs
• Existence and nonexistence of universal graphs
• Feasible Graphs and Colorings
• Graph theoretic uncertainty and feasibility
• Universal graphs and induced-universal graphs
• Universal lines in graphs

Cites work

• scientific article; zbMATH DE number 4087025 (Why is no real title available?)
• scientific article; zbMATH DE number 176212 (Why is no real title available?)
• scientific article; zbMATH DE number 176213 (Why is no real title available?)
• scientific article; zbMATH DE number 1302879 (Why is no real title available?)
• scientific article; zbMATH DE number 1303200 (Why is no real title available?)
• scientific article; zbMATH DE number 806746 (Why is no real title available?)
• scientific article; zbMATH DE number 3311755 (Why is no real title available?)
• Classical recursion theory. Vol. II
• Complexity-theoretic algebra. II: Boolean algebras
• Every recursive linear ordering has a copy in DTIME-SPACE(n,log(n))
• Feasible Graphs and Colorings
• Polynomial-time Abelian groups
• Polynomial-time versus recursive models
• Recursively presented games and strategies

Cited in

(1)

• Complexity and categoricity

This page was built for publication: Feasible graphs with standard universe

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