SIMPLE LINEAR-TIME ALGORITHMS TO TEST CHORDALITY OF GRAPHS, TEST ACYCLICITY OF HYPERGRAPHS, AND SELECTIVELY REDUCE ACYCLIC HYPERGRAPHS.

Robert E. Tarjan, Mihalis Yannakakis

Research output: Contribution to journalArticle

634 Scopus citations

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 languageEnglish (US)
Pages (from-to)566-579
Number of pages14
JournalSIAM Journal on Computing
Volume13
Issue number3
DOIs
StatePublished - Jan 1 1984
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

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