Algorithmic Aspects of Vertex Elimination on Graphs
DOI10.1137/0205021zbMATH Open0353.65019DBLPjournals/siamcomp/RoseTL76OpenAlexW2086119402WikidataQ56016677 ScholiaQ56016677MaRDI QIDQ4124209FDOQ4124209
Authors: George S. Lueker, Donald J. Rose, Robert E. Tarjan
Publication date: 1976
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/17d87b9ac0bedad64489022ef415df05829843ad
Direct numerical methods for linear systems and matrix inversion (65F05) Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99)
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)