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)

A Characterisation of the Minimal Triangulations of Permutation Graphs
Treewidth and minimum fill-in on permutation graphs in linear time
On end-vertices of lexicographic breadth first searches
Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs
Organizing the atoms of the clique separator decomposition into an atom tree
Minimal proper interval completions
Minimal split completions
On a property of minimal triangulations
A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs
A general label search to investigate classical graph search algorithms
Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds
Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models
On minimal augmentation of a graph to obtain an interval graph
Enumeration of the perfect sequences of a chordal graph
Finding large holes
A vertex incremental approach for maintaining chordality
Minimal fill in O(\(n^{2.69}\)) time
A parallel graph partitioning algorithm for a message-passing multiprocessor
Subclasses of \(k\)-trees: characterization and recognition
Generating and characterizing the perfect elimination orderings of a chordal graph
On treewidth and minimum fill-in of asteroidal triple-free graphs
The induced path function, monotonicity and betweenness
Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs
On the structure of (\(P_{5}\),\,gem)-free graphs
LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
Retracts of products of chordal graphs
On the classes of interval graphs of limited nesting and count of lengths
Separability generalizes Dirac's theorem
A note on odd/even cycles
A practical algorithm for making filled graphs minimal
An introduction to clique minimal separator decomposition
Graph extremities defined by search algorithms
Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time
Maximum independent set and maximum clique algorithms for overlap graphs
Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width
Fast minimal triangulation algorithm using minimum degree criterion
Extending partial representations of subclasses of chordal graphs
Revisiting decomposition by clique separators
A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph
A chordal preconditioner for large-scale optimization
Partition refinement techniques: an interesting algorithmic tool kit
Decomposition by maxclique separators
Minimal comparability completions of arbitrary graphs
Practical and efficient split decomposition via graph-labelled trees
Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases
Polynomially bounded algorithms for locatingp-centers on a tree
Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network
Counting the number of independent sets in chordal graphs
Some aspects of perfect elimination orderings in chordal graphs
Dynamic coloring on restricted graph classes
Tractability of most probable explanations in multidimensional Bayesian network classifiers
Moplex orderings generated by the LexDFs algorithm
Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs
Ramified rectilinear polygons: coordinatization by dendrons
On cocolourings and cochromatic numbers of graphs
Proper Interval Vertex Deletion
Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree
Minimal free resolutions of linear edge ideals
\((i,j)\) competition graphs
On some simplicial elimination schemes for chordal graphs
A fully dynamic graph algorithm for recognizing interval graphs
On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs
Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem
An inertia formula for Hermitian matrices with sparse inverses
LexBFS-orderings and powers of chordal graphs
Algorithmic aspects of intersection graphs and representation hypergraphs
Arboricity and bipartite subgraph listing algorithms
On the consecutive ones property
Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs
A local approach to concept generation
Clique coloring \(B_1\)-EPG graphs
A linear-time algorithm for clique-coloring problem in circular-arc graphs
Ninth and tenth order virial coefficients for hard spheres in \(D\) dimensions
Laminar structure of ptolemaic graphs with applications
Strict chordal and strict split digraphs
On sequential heuristic methods for the maximum independent set problem
Medians in median graphs and their cube complexes in linear time
A faster algorithm to recognize undirected path graphs
Tree-decompositions with bags of small diameter
End-vertices of LBFS of (AT-free) bigraphs
Two characterisations of the minimal triangulations of permutation graphs
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

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)