scientific article; zbMATH DE number 554762

Publication date: 2 January 1995

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

Cholesky factorization sparse linear systems chordal graphs minimum spanning tree clique trees Prim's algorithm graph separators acyclic hypergraphs maximum cardinality search

Mathematics Subject Classification ID

Computational methods for sparse matrices (65F50) Analysis of algorithms and problem complexity (68Q25) Factorization of matrices (15A23) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Related Items

Linear-Time Generation of Random Chordal Graphs, Proximity Search for Maximal Subgraph Enumeration, Computing the clique-separator graph for an interval graph in linear time, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Decomposition Methods for Sparse Matrix Nearness Problems, Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables, Solving polynomial least squares problems via semidefinite programming relaxations, Graph Bisection with Pareto Optimization, An efficient algorithm for counting Markov equivalent DAGs, Bears with hats and independence polynomials, Distributed minimum vertex coloring and maximum independent set in chordal graphs, Minimum Average Distance Clique Trees, Chordal Networks of Polynomial Ideals, Linear optimization over homogeneous matrix cones, Partial Lasserre relaxation for sparse Max-Cut, Independent set under a change constraint from an initial solution, Toughness and Hamiltonicity of strictly chordal graphs, Unnamed Item, Recognizing k -Leaf Powers in Polynomial Time, for Constant k, A story of diameter, radius, and (almost) Helly property, Unnamed Item, Galactic token sliding, Chordal graphs and their clique graphs, Graph Bipartization Problem with Applications to Via Minimization in VLSI Design, A Correlatively Sparse Lagrange Multiplier Expression Relaxation for Polynomial Optimization, A Characterisation of the Minimal Triangulations of Permutation Graphs, Treewidth versus clique number. II: Tree-independence number, Eccentricity spectral radius of \(t\)-clique trees with given diameter, Finding biclique partitions of co-chordal graphs, A Multigrid Approach to SDP Relaxations of Sparse Polynomial Optimization Problems, Several improved asymptotic normality criteria and their applications to graph polynomials, Strictly chordal graphs: structural properties and integer Laplacian eigenvalues, Exploiting sparsity for semi-algebraic set volume computation, Counting and enumerating unlabeled split–indifference graphs, Revisiting Decomposition by Clique Separators, Reconfiguration of cliques in a graph, A Local Inverse Formula and a Factorization, Fair allocation of indivisible items with conflict graphs, Moplex orderings generated by the LexDFs algorithm, An efficient representation of chordal graphs, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Searching for better fill-in, Extracting constrained 2-interval subsets in 2-interval sets, Chordal-TSSOS: A Moment-SOS Hierarchy That Exploits Term Sparsity with Chordal Extension, Recognizing Proper Tree-Graphs, Tree decomposition and discrete optimization problems: a survey, Formulas for counting acyclic digraph Markov equivalence classes, Intersection graphs of non-crossing paths, Characterizing Markov equivalence classes for AMP chain graph models, Maximal sub-triangulation in pre-processing phylogenetic data, Deterministic inverse zero-patterns, A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs, On the complexity of the positive semidefinite zero forcing number, A tight approximation algorithm for the cluster vertex deletion problem, Algorithm 996, Junction trees of general graphs, A tight approximation algorithm for the cluster vertex deletion problem, Subset feedback vertex set in chordal and split graphs, Fast Implementation of the Traveling-Salesman-Problem Method for Reordering Columns within Supernodes, Exploiting Chordal Structure in Polynomial Ideals: A Gröbner Bases Approach, Distributed Minimum Vertex Coloring and Maximum Independent Set in Chordal Graphs, Unnamed Item, On some simplicial elimination schemes for chordal graphs, Rank inequalities for positive semidefinite matrices, Block-indifference graphs: characterization, structural and spectral properties, Unnamed Item, The symmetric \(N\)-matrix completion problem, Multiplicity adjustment for temporal and spatial scan statistics using Markov property, Unnamed Item, Unnamed Item, Finding a Maximum-Weight Convex Set in a Chordal Graph, Generalized chordality, vertex separators and hyperbolicity on graphs, Tree decompositions and social graphs, Semi-dynamic algorithms for strongly chordal graphs, Unnamed Item, On the maximum number of edges in chordal graphs of bounded degree and matching number, Fast Diameter Computation within Split Graphs, Totally nonpositive completions on partial matrices, Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, A local method for identifying causal relations under Markov equivalence, Structural balance and interpersonal appraisals dynamics: beyond all-to-all and two-faction networks, Generating and characterizing the perfect elimination orderings of a chordal graph, Sum of squares method for sensor network localization, Treewidth distance on phylogenetic trees, Finding minimum height elimination trees for interval graphs in polynomial time, A clique tree algorithm for partitioning a chordal graph into transitive subgraphs, The scattering number of strictly chordal graphs: linear time determination, Doubly nonnegative relaxations for quadratic and polynomial optimization problems with binary and box constraints, Sparse noncommutative polynomial optimization, Strictly interval graphs: characterization and linear time recognition, A characterization of Markov equivalence classes for acyclic digraphs, Counting and sampling orientations on chordal graphs, Clique neighborhoods and nearly chordal graphs, Improving on the maximum likelihood estimators of the means in Poisson decomposable graphical models, Graph searches and their end vertices, Graph extremities defined by search algorithms, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, Multigraph representations of hierarchical loglinear models, Exploiting sparsity for the min \(k\)-partition problem, Structural conditions for cycle completable graphs, A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables, Resource allocation with time intervals, On strictly chordality-\(k\) graphs, A width parameter useful for chordal and co-comparability graphs, Two characterisations of the minimal triangulations of permutation graphs, Chordal digraphs, Complexity of finding maximum regular induced subgraphs with prescribed degree, 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, Polynomial-time algorithms for subgraph isomorphism in small graph classes of perfect graphs, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, \(N\)-matrix completion problem., Enclosing ellipsoids and elliptic cylinders of semialgebraic sets and their application to error bounds in polynomial optimization, Recursive sum-product algorithm for generalized outer-planar graphs, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, A fully dynamic graph algorithm for recognizing interval graphs, Robust principal component analysis using facial reduction, The \(N\)-matrix completion problem under digraphs assumptions., Computing the null space of finite element problems, Sparse quasi-Newton updates with positive definite matrix completion, Counting the number of independent sets in chordal graphs, Integer Laplacian eigenvalues of chordal graphs, The distance energy of clique trees, Exploiting term sparsity in noncommutative polynomial optimization, Two methods for the generation of chordal graphs, Complexity of the cluster deletion problem on subclasses of chordal graphs, Generating and counting unlabeled \(k\)-path graphs, New results on Ptolemaic graphs, Vulnerability of subclasses of chordal graphs, Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph, Compatibility, desirability, and the running intersection property, Clique trees of infinite locally finite chordal graphs, Detecting fixed patterns in chordal graphs in polynomial time, A new algorithm for decomposition of graphical models, An improved Hara-Takamura procedure by sharing computations on junction tree in Gaussian graphical models, Separator orders in interval, cocomparability, and AT-free graphs, MCMC using Markov bases for computing \(p\)-values in decomposable log-linear models, Minimum fill-in of sparse graphs: kernelization and approximation, A note on minimal d-separation trees for structural learning, A parallel interior point decomposition algorithm for block angular semidefinite programs, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Complexity of the packing coloring problem for trees, The totally positive completion problem, Fast minimal triangulation algorithm using minimum degree criterion, Computing role assignments of chordal graphs, Enumeration of the perfect sequences of a chordal graph, A direct proof for the matrix decomposition of chordal-structured positive semidefinite matrices, Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network, A divide-and-conquer algorithm for generating Markov bases of multi-way tables, The doubly negative matrix completion problem, Exploiting sparsity in linear and nonlinear matrix inequalities via positive semidefinite matrix completion, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, A simple algorithm to find Hamiltonian cycles in proper interval graphs, Non-inclusion and other subclasses of chordal graphs, Positive polynomials on projective limits of real algebraic varieties, A note on sparse SOS and SDP relaxations for polynomial optimization problems over symmetric cones, The completable digraphs for the totally nonnegative completion problem, A clique-difference encoding scheme for labelled \(k\)-path graphs, Chordal decomposition in operator-splitting methods for sparse semidefinite programs, Solving sparse polynomial optimization problems with chordal structure using the sparse bounded-degree sum-of-squares hierarchy, Recognizing underlying sparsity in optimization, Ambush cops and robbers, \(N_0\) completions on partial matrices, Correlative sparsity in primal-dual interior-point methods for LP, SDP, and SOCP, The clique-separator graph for chordal graphs, Avoidable vertices and edges in graphs: existence, characterization, and applications, Bregman primal-dual first-order method and application to sparse semidefinite programming, Exploiting sparsity in complex polynomial optimization, \(P\)-matrix completions under weak symmetry assumptions, Sequential sampling of junction trees for decomposable graphs, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, The symmetric inverse \(M\)-matrix completion problem, Intersection graphs of induced subtrees of any graph and a generalization of chordal graphs, Local inversion of matrices with sparse inverses, Choosing better variable orderings for cylindrical algebraic decomposition via exploiting chordal structure