Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs

DOI10.1137/0213035zbMath0545.68062OpenAlexW1991477862WikidataQ90315968 ScholiaQ90315968MaRDI QIDQ3335007

Mihalis Yannakakis, Robert Endre Tarjan

Publication date: 1984

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0213035

zbMATH Keywords

graph algorithmsparse Gaussian eliminationgraph searchChordal graphsacyclic hypergraphsacyclic data base scheme

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Hypergraphs (05C65) Graph theory (including graph drawing) in computer science (68R10) Information storage and retrieval of data (68P20) Direct numerical methods for linear systems and matrix inversion (65F05)

Related Items (only showing first 100 items - show all)

Powers of hhd-free graphs^∗ ⋮ The Power of Local Consistency in Conjunctive Queries and Constraint Satisfaction Problems ⋮ Optimal In-place Algorithms for Basic Graph Problems ⋮ Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs ⋮ Minimal elimination of planar graphs ⋮ Graphical Models and Message-Passing Algorithms: Some Introductory Lectures ⋮ Semantic Acyclicity on Graph Databases ⋮ Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects ⋮ DISTRIBUTED INFERENCE IN BAYESIAN NETWORKS ⋮ Linearizing partial search orders ⋮ Linear optimization over homogeneous matrix cones ⋮ Quasi-optimal recombination operator ⋮ Wheel-Free Deletion Is W[2-Hard] ⋮ A story of diameter, radius, and (almost) Helly property ⋮ A new global algorithm for max-cut problem with chordal sparsity ⋮ Chordal graphs and their clique graphs ⋮ On Strong Tree-Breadth ⋮ Edge deletion to tree-like graph classes ⋮ How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms ⋮ Unnamed Item ⋮ Dually chordal graphs ⋮ On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints ⋮ Unnamed Item ⋮ Twins in Subdivision Drawings of Hypergraphs ⋮ Computing the decomposable entropy of belief-function graphical models ⋮ On domination elimination orderings and domination graphs ⋮ Generalized cut trees for edge-connectivity ⋮ Listing all spanning trees in Halin graphs — sequential and Parallel view ⋮ On the structure of (pan, even hole)‐free graphs ⋮ Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime ⋮ Revisiting Decomposition by Clique Separators ⋮ Solving Graph Problems via Potential Maximal Cliques ⋮ Network-Based Approximate Linear Programming for Discrete Optimization ⋮ Path-Based Supports for Hypergraphs ⋮ Blocks of Hypergraphs ⋮ Satisfiability of Acyclic and almost Acyclic CNF Formulas (II) ⋮ Linear time algorithms for dominating pairs in asteroidal triple-free graphs ⋮ Dynamic Branching in Qualitative Constraint Networks via Counting Local Models ⋮ A REVIEW OF TREE CONVEX SETS TEST ⋮ Detecting induced subgraphs ⋮ The algorithmic use of hypertree structure and maximum neighbourhood orderings ⋮ Retracts of Products of Chordal Graphs ⋮ Restricted unimodular chordal graphs ⋮ A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs ⋮ Accelerating chromosome evaluation for partial abductive inference in Bayesian networks by means of explanation set absorption ⋮ Disjoint clique cutsets in graphs without long holes ⋮ Complexity classification of some edge modification problems ⋮ On Generating All Maximal Acyclic Subhypergraphs with Polynomial Delay ⋮ On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs ⋮ Diameter determination on restricted graph families ⋮ Unnamed Item ⋮ Triangulation of Bayesian networks by retriangulation ⋮ On the (Non-)existence of Polynomial Kernels for P l -free Edge Modification Problems ⋮ A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs ⋮ Graph transformations preserving the stability number ⋮ Efficient local updates for undirected graphical models ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Cycle-connected mixed graphs and related problems ⋮ A tight approximation algorithm for the cluster vertex deletion problem ⋮ Unnamed Item ⋮ Characterizing Marginalization and Incremental Operations on the Bayes Tree ⋮ Polynomial Kernels for Proper Interval Completion and Related Problems ⋮ Contracting chordal graphs and bipartite graphs to paths and trees ⋮ Triangulation Heuristics for BN2O Networks ⋮ Unnamed Item ⋮ Heuristic and metaheuristic methods for computing graph treewidth ⋮ Exact or approximate inference in graphical models: why the choice is dictated by the treewidth, and how variable elimination can be exploited ⋮ Characterizing path graphs by forbidden induced subgraphs ⋮ The Recognition Problem of Graph Search Trees ⋮ Decomposable Probabilistic Influence Diagrams ⋮ Unnamed Item ⋮ Uniform Constraint Satisfaction Problems and Database Theory ⋮ Graph Classes and Forbidden Patterns on Three Vertices ⋮ Tree decompositions and social graphs ⋮ MCMC model determination for discrete graphical models ⋮ Unnamed Item ⋮ Coloring Meyniel graphs in linear time ⋮ Extremities and orderings defined by generalized graph search algorithms ⋮ Simple vertex ordering characterizations for graph search ⋮ Unnamed Item ⋮ Fast Diameter Computation within Split Graphs ⋮ Preferences Single-Peaked on a Tree: Multiwinner Elections and Structural Results ⋮ Minimal triangulations of graphs: a survey ⋮ A linear time algorithm to list the minimal separators of chordal graphs ⋮ Minimal fill in O(\(n^{2.69}\)) time ⋮ Chordless paths through three vertices ⋮ On neighbourhood singleton-style consistencies for qualitative spatial and temporal reasoning ⋮ Neighborhood perfect graphs ⋮ A generalization of chordal graphs and the maximum clique problem ⋮ \(k\)-NLC graphs and polynomial algorithms ⋮ Computing the union join and subset graph of acyclic hypergraphs in subquadratic time ⋮ I/O-efficient algorithms for graphs of bounded treewidth ⋮ The recognition of geodetically connected graphs ⋮ A complete axiomatization of full acyclic join dependencies ⋮ Distributed revision of composite beliefs ⋮ Existence of extensions and product extensions for discrete probability distributions ⋮ Network-based heuristics for constraint-satisfaction problems ⋮ Chordal graph recognition is in NC ⋮ Forbidden induced subgraphs of normal Helly circular-arc graphs: characterization and detection ⋮ Symbolic techniques in satisfiability solving

This page was built for publication: Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs