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 (only showing first 100 items - show all)

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 ⋮ Vine copula structure representations using graphs and matrices ⋮ 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

This page was built for publication: