Abstract
The authors develop a simplified linear-time test for graph chordality and hypergraph acyclicity. The test uses a new kind of graph (and hypergraph) search, which they call maximum cardinality search. A variant of the method gives a way to selectively reduce acyclic hypergraphs, which is needed for evaluating queries in acyclic relational data bases.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 566-579 |
| Number of pages | 14 |
| Journal | SIAM Journal on Computing |
| Volume | 13 |
| Issue number | 3 |
| DOIs | |
| State | Published - 1984 |
| Externally published | Yes |
All Science Journal Classification (ASJC) codes
- General Computer Science
- General Mathematics
Fingerprint
Dive into the research topics of 'SIMPLE LINEAR-TIME ALGORITHMS TO TEST CHORDALITY OF GRAPHS, TEST ACYCLICITY OF HYPERGRAPHS, AND SELECTIVELY REDUCE ACYCLIC HYPERGRAPHS.'. Together they form a unique fingerprint.Cite this
- APA
- Author
- BIBTEX
- Harvard
- Standard
- RIS
- Vancouver