NP-complete problems simplified on tree schemas

DOI10.1007/BF00289414zbMath0523.68035MaRDI QIDQ1056539

Oded Shmueli, Nathan Goodman

Publication date: 1983

Published in: Acta Informatica (Search for Journal in Brave)

zbMATH Keywords

NP-complete problemsrelational databasesatisfiabilityminimum coverhypergraph coloringtree schemas

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Related Items (1)

The tree projection theorem and relational query processing

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

This page was built for publication: NP-complete problems simplified on tree schemas