Networks · 1993 · 50 citations · 20 references
Natural SciencesComputer ScienceMathematicsAlgorithmsCombinatoricsDiscrete MathematicsDirected Acyclic GraphsGraph AlgorithmsGraph TheoryHypergraph TheoryAcyclic HypergraphsGeometric Graph TheoryPolynomial Time ComplexityPolynomial-time AlgorithmsPolynomial-time ReductionsSteiner Tree ProblemTree Algorithms
Abstract A new class of chordal graphs, containing the class of strongly chordal graphs, is introduced. It is shown that these graphs, called doubly chordal graphs, are related to acyclic hypergraphs and are recognizable in polynomial time. Furthermore, after proving that the Steiner tree and the connected domination problems are polynomially solvable for doubly chordal graphs, it is shown that both problems are NP‐hard for a class of chordal graphs (called Helly chordal graphs) containing the class of doubly chordal graphs. © 1993 John Wiley & Sons, Inc.
20
On the Desirability of Acyclic Database Schemes
Catriel Beeri, Ronald Fagin, David Maier et al. · Journal of the ACM · 1983 · 817 citations · Full text
Algorithms for acyclic database schemes
Mihalis Yannakakis · Very Large Data Bases · 1981 · 500 citations