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

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, Interaction-free multivalued dependency sets, On hypergraph acyclicity and graph chordality, Maximal chordal subgraphs, Tree clustering for constraint networks, Algorithmic aspects of intersection graphs and representation hypergraphs, A note on odd/even cycles, Recognizing single-peaked preferences on a tree, Structural conditions for cycle completable graphs, Satisfiability of acyclic and almost acyclic CNF formulas, Polynomial kernels for proper interval completion and related problems, Static and dynamic source locations in undirected networks, A general label search to investigate classical graph search algorithms, Finding clubs in graph classes, Discovering a junction tree behind a Markov network by a greedy algorithm, Organizing the atoms of the clique separator decomposition into an atom tree, Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, Bayesian network inference using marginal trees, Equivalence between hypergraph convexities, A tie-break model for graph search, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, High dimensional posterior convergence rates for decomposable graphical models, Isomorphism testing of k-trees is in NC, for fixed k, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, Path-based supports for hypergraphs, A universal table model for categorical databases, A logic-based analysis of Dempster-Shafer theory, The graph formulation of the union-closed sets conjecture, Faster parameterized algorithms for \textsc{Minimum Fill-in}, Representations of graphs and networks (coding, layouts and embeddings), Some aspects of the semi-perfect elimination, Counting the number of independent sets in chordal graphs, Cycle-free partial orders and chordal comparability graphs, Finding large holes, Temporal constraint networks, Computing cooperative solution concepts in coalitional skill games, A note on lexicographic breadth first search for chordal graphs, \(K_{1,3}\)-free and \(W_4\)-free graphs, On the effective implementation of the iterative proportional fitting procedure, Peakless functions on graphs, Polarity of chordal graphs, Cycle structure of edge labelled graphs, Iterative proportional scaling via decomposable submodels for contingency tables, Enumerating the decomposable neighbors of a decomposable graph under a simple perturbation scheme, A new algorithm for decomposition of graphical models, Treewidth computations. I: Upper bounds, Hypertree decompositions and tractable queries, Graph connectivity and its augmentation: Applications of MA orderings, Studies on hypergraphs. I: Hyperforests, The induced path function, monotonicity and betweenness, A note on minimal d-separation trees for structural learning, Dynamic programming and planarity: improved tree-decomposition based algorithms, Treewidth computations. II. Lower bounds, Fast minimal triangulation algorithm using minimum degree criterion, On listing, sampling, and counting the chordal graphs with edge constraints, Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs, New lower bounds for bin packing problems with conflicts, Enumeration of the perfect sequences of a chordal graph, Chordality properties on graphs and minimal conceptual connections in semantic data models, On the complexity of signed and minus total domination in graphs, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, On the maximum cardinality search lower bound for treewidth, Efficient algorithms for network localization using cores of underlying graphs, A linear time recognition algorithm for proper interval graphs, A characterization of finite fd-acyclicity, Perspectives on the theory and practice of belief functions, A fast algorithm for query optimization in universal-relation databases, The clique-separator graph for chordal graphs, Laminar structure of ptolemaic graphs with applications, Fast Bayes and the dynamic junction forest, Arboricity: an acyclic hypergraph decomposition problem motivated by database theory, Minimal vertex separators of chordal graphs, Canonical and monophonic convexities in hypergraphs, On 3-Steiner simplicial orderings, The forbidden subgraph characterization of directed vertex graphs, Interval graphs and related topics, Partitioning a chordal graph into transitive subgraphs for parallel sparse triangular solution, Computing the maximum-entropy extension of given discrete probability distributions, Recognizing different types of beta-cycles in a database scheme, The maximum clique problem, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, Decomposing constraint satisfaction problems using database techniques, Hybrid backtracking bounded by tree-decomposition of constraint networks, An algorithm for determining minimal reduced-coverings of acyclic database schemes, Optimal decomposition by clique separators, A faster algorithm to recognize undirected path graphs, Recognizing graph search trees, Generating and characterizing the perfect elimination orderings of a chordal graph, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, Partition search for non-binary constraint satisfaction, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Finding minimum height elimination trees for interval graphs in polynomial time, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Clique tree generalization and new subclasses of chordal graphs, New linear time algorithms for generating perfect elimination orderings of chordal graphs, Restricted triangulation on circulant graphs, Probability propagation, Information and probabilistic reasoning, \(r\)-dominating cliques in graphs with hypertree structure, Decomposition in multidimensional Boolean-optimization problems with sparse matrices, Prim-based support-graph preconditioners for min-cost flow problems, LexBFS-orderings and powers of chordal graphs, Graph extremities defined by search algorithms, Computing a clique tree with the algorithm maximal label search, The existence of homeomorphic subgraphs in chordal graphs, Default reasoning using classical logic, Multigraph representations of hierarchical loglinear models, A special case for subset interconnection designs, Complexity and approximability of the happy set problem, Perfect elimination orderings for symmetric matrices, Estimating the number of connected components in a graph via subgraph sampling, On computing minimal models, Vertices removal for feasibility of clustered spanning trees, An algorithm for coloring some perfect graphs, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, The algorithmic use of hypertree structure and maximum neighbourhood orderings, An adaptive reasoning approach towards effficient ordering of composite hypotheses, Hadwiger Number of Graphs with Small Chordality, Beyond Helly graphs: the diameter problem on absolute retracts, Handling multiple sources of variation using influence diagrams, Separability generalizes Dirac's theorem, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Sequences of regressions and their independences, On the impact of running intersection inequalities for globally solving polynomial optimization problems, Computing partial hypergraphs of bounded width, Hypergraph incidence coloring, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, On the (non-)existence of polynomial kernels for \(P _{l }\)-free edge modification problems, A decomposition algorithm for learning Bayesian networks based on scoring function, Combining restarts, nogoods and bag-connected decompositions for solving csps, Decomposable convexities in graphs and hypergraphs, Some results on the target set selection problem, A fully dynamic graph algorithm for recognizing interval graphs, Moplex orderings generated by the LexDFs algorithm, Searching for better fill-in, On spectrum assignment in elastic optical tree-networks, Extracting constrained 2-interval subsets in 2-interval sets, Decomposition of structural learning about directed acyclic graphs, Unifying tree decompositions for reasoning in graphical models, The difficulty of being moral, Efficiently enumerating minimal triangulations, Tree decompositions of graphs: saving memory in dynamic programming, Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph, Latent association graph inference for binary transaction data, Homology cycles and dependent cycles of hypergraphs, Detecting fixed patterns in chordal graphs in polynomial time, Inclusion/exclusion meets measure and conquer, Tree decomposition and discrete optimization problems: a survey, Tree-decomposition based heuristics for the two-dimensional bin packing problem with conflicts, On the structure of (\(P_{5}\),\,gem)-free graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, Spanning trees and identifiability of a single-factor model, Ninth and tenth order virial coefficients for hard spheres in \(D\) dimensions, Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network, Graph classes and approximability of the happy set problem, Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals, Computing vertex-disjoint paths in large graphs using MAOs, Bayesian Approaches for Large Biological Networks, Variable neighborhood search for graphical model energy minimization, Subexponential parameterized algorithms and kernelization on almost chordal graphs, On the Power of Graph Searching for Cocomparability Graphs, Paired threshold graphs, Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Inference in belief networks: A procedural guide, Dynamic branching in qualitative constraint-based reasoning via counting local models, Perfect elimination orderings of chordal powers of graphs, Avoidable vertices and edges in graphs: existence, characterization, and applications, On the semi-perfect elimination, Learning tractable Bayesian networks in the space of elimination orders, Attachment centrality: measure for connectivity in networks, Evaluating Datalog via tree automata and cycluits, Exploiting Separators for Guiding VNS, Conjunctive query containment revisited, Bayesian networks: the minimal triangulations of a graph, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs, Collective singleton-based consistency for qualitative constraint networks: theory and practice, A practical algorithm for making filled graphs minimal, Computing marginals for arbitrary subsets from marginal representation in Markov trees, Modifying a graph using vertex elimination, Linear-time algorithms for tree root problems, A faster algorithm to recognize even-hole-free graphs, An implementation of the iterative proportional fitting procedure by propagation trees., ProCount: weighted projected model counting with graded project-join trees