NP-complete problems simplified on tree schemas
From MaRDI portal
Publication:1056539
DOI10.1007/BF00289414zbMath0523.68035MaRDI QIDQ1056539
Publication date: 1983
Published in: Acta Informatica (Search for Journal in Brave)
NP-complete problems; relational database; satisfiability; minimum cover; hypergraph coloring; tree schemas
68Q25: Analysis of algorithms and problem complexity
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Connections in acyclic hypergraphs
- Acyclic join dependency and data base projections
- Testing the universal instance assumption
- A characterisation of rigid circuit graphs
- On the Desirability of Acyclic Database Schemes
- Degrees of acyclicity for hypergraphs and relational database schemes
- Syntactic Characterization of Tree Database Schemas
- Maximal objects and the semantics of universal relation databases
- On Determining Tree Query Membership Of A Distributed Query
- Using Semi-Joins to Solve Relational Queries
- Power of Natural Semijoins
- A simplied universal relation assumption and its properties
- Tree queries
- Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph