Optimal decomposition by clique separators

DOI10.1016/0012-365X(93)90510-ZzbMath0793.05128MaRDI QIDQ2366013

Hanns-Georg Leimer

Publication date: 29 June 1993

Published in: Discrete Mathematics (Search for Journal in Brave)

zbMATH Keywords

decompositionsclique separatorsprime subgraphs

Mathematics Subject Classification ID

Applications of graph theory (05C90) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (05C99)

Related Items

Safe separators for treewidth, Complexity aspects of the triangle path convexity, Characterizing atoms that result from decomposition by clique separators, A necessary condition for the equality of the clique number and the convexity number of a graph, Bounds for cell entries in contingency tables given marginal totals and decomposable graphs, Computing the union join and subset graph of acyclic hypergraphs in subquadratic time, Representing a concept lattice by a graph, All roads lead to Rome -- new search methods for the optimal triangulation problem, On CLIQUE Problem for Sparse Graphs of Large Dimension, Two classes of graphs in which some problems related to convexity are efficiently solvable, Partial inversion for linear systems and partial closure of independence graphs, Computing the hull number in toll convexity, Unnamed Item, On decomposability of multilinear sets, Statistical Inference in Context Specific Interaction Models for Contingency Tables, Applying clique-decomposition for computing Gromov hyperbolicity, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, An improved isomorphism test for bounded-tree-width graphs, Structural conditions for cycle completable graphs, On the monophonic rank of a graph, Organizing the atoms of the clique separator decomposition into an atom tree, On the geodetic iteration number of a graph in which geodesic and monophonic convexities are equivalent, Equivalence between hypergraph convexities, The maximum infection time in the geodesic and monophonic convexities, Computing the hull and interval numbers in the weakly toll convexity, Unnamed Item, Structural learning for Bayesian networks by testing complete separators in prime blocks, Fixed-Parameter Tractable Canonization and Isomorphism Test for Graphs of Bounded Treewidth, Algorithms for convex hull finding in undirected graphical models, Revisiting Decomposition by Clique Separators, Decomposable convexities in graphs and hypergraphs, Unnamed Item, Decomposition by maxclique separators, Trees of tangles in abstract separation systems, Maximal prime subgraph decomposition of Bayesian networks: A relational database perspective, Inapproximability results related to monophonic convexity, CHARACTERISTIC PROPERTIES AND RECOGNITION OF GRAPHS IN WHICH GEODESIC AND MONOPHONIC CONVEXITIES ARE EQUIVALENT, A new algorithm for decomposition of graphical models, An improved Hara-Takamura procedure by sharing computations on junction tree in Gaussian graphical models, A note on minimal d-separation trees for structural learning, A Localization Approach to Improve Iterative Proportional Scaling in Gaussian Graphical Models, A divide-and-conquer algorithm for generating Markov bases of multi-way tables, Finding cut-vertices in the square roots of a graph, Decomposition of two classes of structural models, Standard imsets for undirected and chain graphical models, Decomposability of abstract and path-induced convexities in hypergraphs, Junction trees of general graphs, Bayesian learning of graphical vector autoregressions with unequal lag-lengths, Finding the minimal set for collapsible graphical models, Hyper Inverse Wishart Distribution for Non-decomposable Graphs and its Application to Bayesian Inference for Gaussian Graphical Models, Decomposition of a hypergraph by partial-edge separators, Evaluating Datalog via tree automata and cycluits, Canonical and monophonic convexities in hypergraphs, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, An implementation of the iterative proportional fitting procedure by propagation trees.

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Simplicial tree-decompositions of infinite graphs. III: The uniqueness of prime decompositions
• On rigid circuit graphs
• Decomposition by clique separators
• Simplicial decompositions of graphs - some uniqueness results
• Simplicial decompositions of graphs: A survey of applications
• Graphical models for associations between variables, some of which are qualitative and some quantitative
• Homomorphiebasen von Graphenmengen
• Markov fields and log-linear interaction models for contingency tables
• Minimal triangulation of a graph and optimal pivoting order in a sparse matrix
• Über simpliziale Zerfällungen beliebiger (endlicher oder unendlicher) Graphen
• Incidence matrices and interval graphs
• Triangulated graphs and the elimination process
• Simplicial tree-decompositions of infinite graphs. I
• Simplicial tree-decompositions of infinite graphs. II: The existence of prime decompositions
• On the Desirability of Acyclic Database Schemes
• Representation of a finite graph by a set of intervals on the real line
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• A Fast Algorithm for Finding an Optimal Ordering for Vertex Elimination on a Graph
• Algorithmic Aspects of Vertex Elimination on Graphs