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
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

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)