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)

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
\(K_ i\)-covers. I: Complexity and polytopes
Parameterized coloring problems on chordal graphs
The algorithmic use of hypertree structure and maximum neighbourhood orderings
Subexponential parameterized algorithms and kernelization on almost chordal graphs
The maximum k-colorable subgraph problem for chordal graphs
End-vertices of graph search algorithms
Recognizing graph search trees
Chordal deletion is fixed-parameter tractable
On 3-Steiner simplicial orderings
Maximal chordal subgraphs
Largest chordal and interval subgraphs faster than \(2^n\)
The forbidden subgraph characterization of directed vertex graphs
Treewidth computations. I: Upper bounds
A survey of the algorithmic aspects of modular decomposition
Practical and efficient circle graph recognition
Graph searches and their end vertices
On the complexity of the positive semidefinite zero forcing number
Computing square roots of trivially perfect and threshold graphs
End vertices of graph searches on bipartite graphs
Differential geometric treewidth estimation in adiabatic quantum computation
On the existence of convex decompositions of partially separable functions
Tree decompositions with small cost
Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones
A review of tree convex sets test
Quasi-threshold graphs
Vertex ordering characterizations of graphs of bounded asteroidal number
Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
A new LBFS-based algorithm for cocomparability graph recognition
On recognition of threshold tolerance graphs and their complements
One-way and round-trip center location problems
Optimal decomposition by clique separators
Certifying algorithms
A direct active set algorithm for large sparse quadratic programs with simple bounds
Perfect edge domination and efficient edge domination in graphs
Covering orthogonal polygons with star polygons: The perfect graph approach
A linear-time algorithm for proper interval graph recognition
Chordless paths through three vertices
Strongly chordal and chordal bipartite graphs are sandwich monotone
Structure and linear time recognition of 3-leaf powers
Maximum induced matchings for chordal graphs in linear time
Extending partial representations of circular-arc graphs
The importance of structure in incomplete factorization preconditioners
Optimal packing and covering in the plane are NP-complete
Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions
On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs
Characterizing path graphs by forbidden induced subgraphs
Finding maximum cliques in arbitrary and in special graphs
\(r\)-dominating cliques in graphs with hypertree structure
The analysis of a nested dissection algorithm
On extremal sizes of locally \(k\)-tree graphs.
A note on perfect partial elimination
Recognition of some perfectly orderable graph classes
New sufficient conditions for \(\alpha\)-redundant vertices
Characterization and Recognition of Partial 3-Trees
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

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)