Approximation and Hardness Results for the Maximum Edges in Transitive Closure Problem.
Anna AdamaszekGuillaume BlinAlexandru PopaPublished in: IWOCA (2014)
Keyphrases
- transitive closure
- directed acyclic graph
- expressive power
- constraint databases
- recursive queries
- query evaluation
- query language
- directed graph
- np hard
- relational algebra
- first order logic
- spatial databases
- np complete
- databases
- phase transition
- data model
- expert systems
- binary relations
- metadata
- artificial intelligence