Triangulated graphs and the elimination process
From MaRDI portal
Publication:2545884
DOI10.1016/0022-247X(70)90282-9zbMath0216.02602MaRDI QIDQ2545884
Publication date: 1970
Published in: Journal of Mathematical Analysis and Applications (Search for Journal in Brave)
Related Items
Powers of hhd-free graphs∗, Chordality Preserving Incremental Triangular Decomposition and Its Implementation, A faster algorithm to recognize undirected path graphs, Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs, Minimal elimination of planar graphs, Convexity in Graphs and Hypergraphs, Canonical representations of partial 2-and 3-trees, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Matrices with chordal inverse zero-patterns, Decomposition Methods for Sparse Matrix Nearness Problems, On strict-double-bound numbers of graphs and cut sets, Characterization and Recognition of Partial 3-Trees, Graphical Models and Message-Passing Algorithms: Some Introductory Lectures, Prim-based support-graph preconditioners for min-cost flow problems, Domain permutation reduction for constraint satisfaction problems, Theory of evidence ? A survey of its mathematical foundations, applications and computational aspects, ?-Perfect graphs, Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, Complexity of Finding Embeddings in a k-Tree, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, Fuzzy chordal graphs and its properties, Minimum Average Distance Clique Trees, Solvability of theories of certain classes of elimination graphs, Space-efficient algorithms for reachability in directed geometric graphs, A cop-winning strategy on strongly cop-win graphs, Fast causal orientation learning in directed acyclic graphs, Discrete cubical and path homologies of graphs, Determinantal formulae and nonsymmetric gaussian perfect elimination, Chordal graphs and their clique graphs, Approximating the chromatic polynomial of a graph, The parallel complexity of elimination ordering procedures, Edgewise strongly shellable clutters, Chordal matroids arising from generalized parallel connections, Sum-of-squares chordal decomposition of polynomial matrix inequalities, Variations of maximum-clique transversal sets on graphs, Operator systems for tolerance relations on finite sets, Revisiting Decomposition by Clique Separators, On Directed and Undirected Propagation Algorithms for Bayesian Networks, A Local Inverse Formula and a Factorization, Two optimal strategies for active learning of causal models from interventional data, On the complexity of the black-and-white coloring problem on some classes of perfect graphs, Solving Graph Problems via Potential Maximal Cliques, Subclasses of \(k\)-trees: characterization and recognition, A sufficiently fast algorithm for finding close to optimal clique trees, A Separator Theorem for Chordal Graphs, Representation characterizations of chordal bipartite graphs, The elimination procedure for the competition number is not optimal, Unnamed Item, Expansions of Chromatic Polynomials and Log-Concavity, Minimal elimination ordering for graphs of bounded degree, Two strikes against perfect phylogeny, Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes, Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach, Heuristic and metaheuristic methods for computing graph treewidth, Nonserial dynamic programming: On the optimal strategy of variable elimination for the rectangular lattice, On the theory of the elimination process, On the Structure of Contractible Vertex Pairs in Chordal Graphs, A counter example to a conjecture of D. J. Rose on minimum triangulation, Several results on chordal bipartite graphs, The intersection graphs of subtrees in trees are exactly the chordal graphs, Decomposable Probabilistic Influence Diagrams, Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph, On the Chordality of Simple Decomposition in Top-Down Style, Minimal separators in \(P_4\)-sparse graphs, A parallel algorithm for computing Steiner trees in strongly chordal graphs, The parallel solution of domination problems on chordal and strongly chordal graphs, Intersection graphs of concatenable subtrees of graphs, Reversible jump MCMC for nonparametric drift estimation for diffusion processes, Heuristics for the network design problem with connectivity requirements, Optimal decomposition by clique separators, Invertible completions of partial operator matrices: The nonsymmetric case, A generalization of chordal graphs and the maximum clique problem, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Chordal editing is fixed-parameter tractable, Bipartite permutation graphs, On the structure of contractible edges in \(k\)-connected partial \(k\)-trees, Metric graphs elastically embeddable in the plane, Probability propagation, A characterization of normal fraternally orientable perfect graphs, Optimal labelling of unit interval graphs, Positive semidefinite matrices with a given sparsity pattern, A sufficient condition to extend polynomial results for the maximum independent set problem, Maximal chordal subgraphs, Graph extremities defined by search algorithms, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, Linear time algorithms for NP-hard problems restricted to partial k- trees, Algorithmic aspects of intersection graphs and representation hypergraphs, Triangulating graphs without asteroidal triples, Algorithmic aspects of the generalized clique-transversal problem on chordal graphs, Intersection graphs of Helly families of subtrees, All-pairs-shortest-length on strongly chordal graphs, Fitting very large sparse Gaussian graphical models, Chordal digraphs, Vector representations of graphs and distinguishing quantum product states with one-way LOCC, On treewidth and minimum fill-in of asteroidal triple-free graphs, Triangulating multitolerance graphs, 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, Weighted maximum-clique transversal sets of graphs, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, A simple algorithm for finding a cycle of length greater than three and without diagonals, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, Chordal graphs in triangular decomposition in top-down style, On minimal augmentation of a graph to obtain an interval graph, Matrix completions and chordal graphs, Decision making with multiple objectives using GAI networks, A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs, Independent domination in chordal graphs, Faster parameterized algorithms for \textsc{Minimum Fill-in}, Strongly chordal and chordal bipartite graphs are sandwich monotone, Inheritance principles for chordal graphs, Digraph measures: Kelly decompositions, games, and orderings, Some aspects of the semi-perfect elimination, Characterizing and computing the structure of clique intersections in strongly chordal graphs, Exploiting partial correlations in distributionally robust optimization, An inertia formula for Hermitian matrices with sparse inverses, Variations of \(Y\)-dominating functions on graphs, Efficiently enumerating minimal triangulations, A simple linear time algorithm for the domatic partition problem on strongly chordal graphs, Learning discrete decomposable graphical models via constraint optimization, An algorithm for fraternal orientation of graphs, Strong elimination ordering of the total graph of a tree, Treewidth computations. I: Upper bounds, A characterization of signed graphs with generalized perfect elimination orderings, Studies on hypergraphs. I: Hyperforests, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, An algorithm for testing chordality of graphs, Signed and minus clique-transversal functions on graphs, A recognition algorithm for the intersection graphs of directed paths in directed trees, Treewidth and minimum fill-in on permutation graphs in linear time, Comparability graphs and a new matroid, On the complexity of signed and minus total domination in graphs, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, Minimal triangulation of a graph and optimal pivoting order in a sparse matrix, Algorithms on clique separable graphs, A note on perfect Gaussian elimination, Positive semidefinite matrix completions on chordal graphs and constraint nondegeneracy in semidefinite programming, Paired threshold graphs, The complexity of generalized clique covering, Counting clique trees and computing perfect elimination schemes in parallel, A remark on perfect Gaussian elimination of symmetric matrices, Recognition of some perfectly orderable graph classes, Extending cycles in graphs, Perspectives on the theory and practice of belief functions, Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition, Avoidable vertices and edges in graphs: existence, characterization, and applications, Minimal vertex separators of chordal graphs, Electrical networks and hyperplane arrangements, Bayesian networks: the minimal triangulations of a graph, The forbidden subgraph characterization of directed vertex graphs, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs, Domination, independent domination, and duality in strongly chordal graphs, Characterizations of strongly chordal graphs, Some aspects of perfect elimination orderings in chordal graphs, On powers and centers of chordal graphs, Positive definite completions of partial Hermitian matrices, Decomposition by clique separators, Efficient algorithms for combinatorial problems on graphs with bounded decomposability - a survey, The maximum clique problem, Listing all potential maximal cliques of a graph, Speeding-up structured probabilistic inference using pattern mining, The complexity of generalized clique packing
Cites Work
