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

Robert E. Tarjan; Mihalis Yannakakis

doi:10.1137/0213035

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 journal › Article › peer-review

749 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 language	English (US)
Pages (from-to)	566-579
Number of pages	14
Journal	SIAM Journal on Computing
Volume	13
Issue number	3
DOIs	https://doi.org/10.1137/0213035
State	Published - 1984
Externally published	Yes

All Science Journal Classification (ASJC) codes

General Computer Science
General Mathematics

Access to Document

10.1137/0213035

Cite this

@article{98dffe8ec7904dd489718e9bfd496654,

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

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.",

author = "Tarjan, {Robert E.} and Mihalis Yannakakis",

year = "1984",

doi = "10.1137/0213035",

language = "English (US)",

volume = "13",

pages = "566--579",

journal = "SIAM Journal on Computing",

issn = "0097-5397",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "3",

}

TY - JOUR

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

AU - Tarjan, Robert E.

AU - Yannakakis, Mihalis

PY - 1984

Y1 - 1984

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0021473698&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0021473698&partnerID=8YFLogxK

U2 - 10.1137/0213035

DO - 10.1137/0213035

M3 - Article

AN - SCOPUS:0021473698

SN - 0097-5397

VL - 13

SP - 566

EP - 579

JO - SIAM Journal on Computing

JF - SIAM Journal on Computing

IS - 3

ER -

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

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this