Algorithmic Aspects of Vertex Elimination on Graphs

DOI10.1137/0205021zbMATH Open0353.65019DBLPjournals/siamcomp/RoseTL76OpenAlexW2086119402WikidataQ56016677 ScholiaQ56016677MaRDI QIDQ4124209FDOQ4124209

Cited In (only showing first 100 items - show all)

Minimal elimination ordering for graphs of bounded degree
A linear time algorithm to list the minimal separators of chordal graphs
On the proper orientation number of chordal graphs
An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time
A survey of direct methods for sparse linear systems
I/O-efficient algorithms for graphs of bounded treewidth
A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring
Heuristic and metaheuristic methods for computing graph treewidth
Chordal graph recognition is in NC
Chordal graphs and their clique graphs
Minimal vertex separators of chordal graphs
Linear-time algorithms for tree root problems
A new algorithm for decomposition of graphical models
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph
Representing triangulated graphs in stars
Recognition of linear and star variants of leaf powers is in P
An \(\mathcal {O}(n^2)\) time algorithm for the minimal permutation completion problem
An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs
The isomorphism problem for \(k\)-trees is complete for logspace
Finding houses and holes in graphs
Cuts, matrix completions and graph rigidity
Triangulated neighborhoods in even-hole-free graphs
Burning two worlds
The solution space of sorting with recurring comparison faults
The recognition problem of graph search trees
Maximum induced matching problem on hhd-free graphs
Weak bipolarizable graphs
Probe Ptolemaic Graphs
Title not available (Why is that?)
The General Minimum Fill-In Problem
On linear and circular structure of (claw, net)-free graphs
An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs
Maximal sub-triangulation in pre-processing phylogenetic data
On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints
On vertex ranking of a starlike graph
Recognizing graphs without asteroidal triples
Robustness to dependency in portfolio optimization using overlapping marginals
Algorithms for unipolar and generalized split graphs
Efficient algorithms for network localization using cores of underlying graphs
Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs
On constructing the elimination tree
Covering, Packing and Generalized Perfection
Classes of perfect graphs
High dimensional posterior convergence rates for decomposable graphical models
A Dynamic Programming Approach to the Dominating Set Problem on k-Trees
Efficient parallel graph algorithms for coarse grained multicomputers and BSP
A polynomial algorithm for the parity path problem on perfectly orientable graphs
MPQ-trees for the orthogonal packing problem
Linear-time generation of random chordal graphs
Estimating the number of connected components in a graph via subgraph sampling
Minimal elimination of planar graphs
Triangulation of Bayesian networks by retriangulation
Convex dominating sets in maximal outerplanar graphs
Recognizing different types of beta-cycles in a database scheme
Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete
Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques
Minimal obstructions for partial representations of interval graphs
Method of fundamental solutions for 3D elasticity with body forces by coupling compactly supported radial basis functions
An implementation of the iterative proportional fitting procedure by propagation trees.
Hybrid backtracking bounded by tree-decomposition of constraint networks
Calculs de complexité relatifs à une méthode de dissection emboîtée
PRM inference using Jaffray \& Faÿ's local conditioning
A note on lexicographic breadth first search for chordal graphs
Computing the Minimum Fill-In is NP-Complete
The maximum clique problem
Fast Constrained Image Segmentation Using Optimal Spanning Trees
Extending the MAX algorithm for maximum independent set
Dismantlability of weakly systolic complexes and applications
Labeling algorithms for domination problems in sun-free chordal graphs
Independent domination in chordal graphs
Some aspects of the semi-perfect elimination
Linear time algorithms for dominating pairs in asteroidal triple-free graphs
A Separator Theorem for Chordal Graphs
Diameter determination on restricted graph families
On the power of graph searching for cocomparability graphs
Minimal dominating sets in graph classes: combinatorial bounds and enumeration
Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs
Exploiting special structure in semidefinite programming: a survey of theory and applications
Decomposition by clique separators
Positive definite completions of partial Hermitian matrices
Fixed-parameter tractability of graph modification problems for hereditary properties
On the semi-perfect elimination
Recognition of perfect elimination bipartite graphs
A generalization of chordal graphs and the maximum clique problem
Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs
Efficient algorithms for minimum weighted colouring of some classes of perfect graphs
On the SPANNING \(k\)-TREE problem
Decomposition of structural learning about directed acyclic graphs
Restricted triangulation on circulant graphs
The recognition of geodetically connected graphs
Consecutive retrieval property -- revisited
Recognizing \(i\)-triangulated graphs in \(O(mn)\) time
A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs
Domination, independent domination, and duality in strongly chordal graphs
Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
Some results on the target set selection problem
A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs
Approximation algorithms for maximum two-dimensional pattern matching
On algorithms for (\(P_5\), gem)-free graphs

This page was built for publication: Algorithmic Aspects of Vertex Elimination on Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4124209)