Testing the universal instance assumption

DOI10.1016/0020-0190(80)90114-3zbMath0422.68048OpenAlexW1981597405MaRDI QIDQ1133903

Richard E. Ladner, Peter Honeyman, Mihalis Yannakakis

Publication date: 1980

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(80)90114-3

zbMATH Keywords

relational databaseNP-completeuniversal relationuniversal instancejoin-consistent

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Information storage and retrieval of data (68P20)

Related Items (10)

Probabilistic satisfiability ⋮ On hypergraph acyclicity and graph chordality ⋮ On minimal constraint networks ⋮ NP-completeness: A retrospective ⋮ Inclusion and equivalence between relational database schemata ⋮ On the representation and querying of sets of possible worlds ⋮ Connection-trap-free database schemes ⋮ Cycle structure of edge labelled graphs ⋮ Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals ⋮ NP-complete problems simplified on tree schemas

Cites Work

• Some simplified NP-complete graph problems
• A relational model of data for large shared data banks
• Unnamed Item
• Unnamed Item

This page was built for publication: Testing the universal instance assumption