Algorithmic Aspects of Vertex Elimination on Graphs
From MaRDI portal
Publication:4124209
DOI10.1137/0205021zbMath0353.65019OpenAlexW2086119402WikidataQ56016677 ScholiaQ56016677MaRDI QIDQ4124209
George S. Lueker, Robert Endre Tarjan, Donald J. Rose
Publication date: 1976
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://semanticscholar.org/paper/17d87b9ac0bedad64489022ef415df05829843ad
Analysis of algorithms and problem complexity (68Q25) Graph theory (05C99) Direct numerical methods for linear systems and matrix inversion (65F05)
Related Items
Lexbfs-orderings and powers of hhd-free graphs∗, Powers of hhd-free graphs∗, Linear-Time Generation of Random Chordal Graphs, Proximity Search for Maximal Subgraph Enumeration, Minimal elimination of planar graphs, On Fault-Tolerant Low-Diameter Clusters in Graphs, Characterization and Recognition of Partial 3-Trees, The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs, Unnamed Item, Strongly Chordal and Chordal Bipartite Graphs Are Sandwich Monotone, An nc algorithm to recognize hhd-free graphs, Efficient parallel graph algorithms for coarse grained multicomputers and BSP, Chordal Networks of Polynomial Ideals, Linearizing partial search orders, Temporal interval cliques and independent sets, Space-efficient algorithms for reachability in directed geometric graphs, Recognition of linear and star variants of leaf powers is in P, Extending partial representations of circular-arc graphs, Linear optimization over homogeneous matrix cones, Coloring rings, Dynamic coloring on restricted graph classes, Shifting paths to avoidable ones, The diameter of AT‐free graphs, Treelength of series-parallel graphs, On the complexity of the storyplan problem, A story of diameter, radius, and (almost) Helly property, Coloring \((4K_1,C_4,C_6)\)-free graphs, Approximating the bandwidth for asteroidal triple-free graphs, Computing and listing avoidable vertices and paths, Exact and parameterized algorithms for restricted subset feedback vertex set in chordal graphs, Chordal graphs and their clique graphs, Exact algorithms for restricted subset feedback vertex set in chordal and split graphs, Approximating the chromatic polynomial of a graph, The parallel complexity of elimination ordering procedures, Dually chordal graphs, A Dynamic Programming Approach to the Dominating Set Problem on k-Trees, Treewidth versus clique number. II: Tree-independence number, Computing and listing avoidable vertices and paths, Finding biclique partitions of co-chordal graphs, Unnamed Item, On Listing, Sampling, and Counting the Chordal Graphs with Edge Constraints, Probe Ptolemaic Graphs, Combinatorial Generation via Permutation Languages. V. Acyclic Orientations, Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs, On domination elimination orderings and domination graphs, Revisiting Decomposition by Clique Separators, Étude de la séparation et de l'élimination sur une famille de graphes quotients déduite d'une méthode de dissections emboîtées, The General Minimum Fill-In Problem, Solving Graph Problems via Potential Maximal Cliques, Chordless Cycle Packing Is Fixed-Parameter Tractable, Parallel QR Factorization of Block-Tridiagonal Matrices, Linear time algorithms for dominating pairs in asteroidal triple-free graphs, A REVIEW OF TREE CONVEX SETS TEST, Detecting induced subgraphs, Recognizing Proper Tree-Graphs, A Posteriori Error Estimates for Multilevel Methods for Graph Laplacians, Retracts of Products of Chordal Graphs, A survey of direct methods for sparse linear systems, Domination graphs: Examples and counterexamples, The lexicographic method for the threshold cover problem, Approximation algorithms for maximum two-dimensional pattern matching, Finding houses and holes in graphs, A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs, On the existence of convex decompositions of partially separable functions, Intersection graphs of non-crossing paths, On the L(h, k)‐labeling of co‐comparability graphs and circular‐arc graphs, Unnamed Item, Diameter determination on restricted graph families, Unnamed Item, Triangulation of Bayesian networks by retriangulation, A Fully Dynamic Graph Algorithm for Recognizing Proper Interval Graphs, Graph transformations preserving the stability number, Minimal elimination ordering for graphs of bounded degree, On the complexity of the positive semidefinite zero forcing number, On \(H\)-topological intersection graphs, A new lower bound for the eternal vertex cover number of graphs, Diameter of colorings under Kempe changes, On the power of BFS to determine a graph's diameter, Linear separation of connected dominating sets in graphs, Unnamed Item, Heuristic and metaheuristic methods for computing graph treewidth, Linear-Time Recognition of Probe Interval Graphs, Characterizing path graphs by forbidden induced subgraphs, Dismantlability of weakly systolic complexes and applications, The Recognition Problem of Graph Search Trees, Iterative methods for linear systems of equations: A brief historical journey, Unnamed Item, Unnamed Item, Commuting projections on graphs, PARTITION REFINEMENT TECHNIQUES: AN INTERESTING ALGORITHMIC TOOL KIT, Graph Classes and Forbidden Patterns on Three Vertices, Tree decompositions and social graphs, Unnamed Item, Unnamed Item, On the Chordality of Simple Decomposition in Top-Down Style, Polynomially bounded algorithms for locatingp-centers on a tree, Maximum Induced Matching Algorithms via Vertex Ordering Characterizations, Computing the Minimum Fill-In is NP-Complete, A vertex incremental approach for maintaining chordality, A linear time algorithm to list the minimal separators of chordal graphs, Minimal fill in O(\(n^{2.69}\)) time, Chordless paths through three vertices, Parameterized coloring problems on chordal graphs, On the proper orientation number of chordal graphs, Row-ordering schemes for sparse Givens transformations. II. Implicit graph model, Neighborhood perfect graphs, A generalization of chordal graphs and the maximum clique problem, I/O-efficient algorithms for graphs of bounded treewidth, The recognition of geodetically connected graphs, Consecutive retrieval property -- revisited, Recognizing \(i\)-triangulated graphs in \(O(mn)\) time, Efficient solutions of hierarchical systems of linear equations, Structure and linear time recognition of 3-leaf powers, A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring, The analysis of a nested dissection algorithm, Largest chordal and interval subgraphs faster than \(2^n\), Differential geometric treewidth estimation in adiabatic quantum computation, Two characterisations of minimal triangulations of \(2K_{2}\)-free graphs, Chordal graph recognition is in NC, The maximum k-colorable subgraph problem for chordal graphs, Sparse linear problems and the least squares method, A new LBFS-based algorithm for cocomparability graph recognition, On recognition of threshold tolerance graphs and their complements, A parallel graph partitioning algorithm for a message-passing multiprocessor, Algorithmique et calculs de complexité pour un solveur de type dissections emboîtées. (Algorithmic study and complexity bounds for a nested dissection solver), Maximal chordal subgraphs, Triangulated neighborhoods in even-hole-free graphs, Recognizing graphs without asteroidal triples, Minimal dominating sets in graph classes: combinatorial bounds and enumeration, A note on perfect partial elimination, Two characterisations of the minimal triangulations of permutation graphs, A general label search to investigate classical graph search algorithms, Organizing the atoms of the clique separator decomposition into an atom tree, Implementation of nonsymmetric interior-point methods for linear optimization over sparse matrix cones, A tie-break model for graph search, Creating non-minimal triangulations for use in inference in mixed stochastic/deterministic graphical models, Minimal free resolutions of linear edge ideals, High dimensional posterior convergence rates for decomposable graphical models, The importance of structure in incomplete factorization preconditioners, Ramified rectilinear polygons: coordinatization by dendrons, Fully dynamic algorithm for chordal graphs with \(O(1)\) query-time and \(O(n^2)\) update-time, Covering orthogonal polygons with star polygons: The perfect graph approach, A survey of the algorithmic aspects of modular decomposition, PRM inference using Jaffray \& Faÿ's local conditioning, Strongly chordal and chordal bipartite graphs are sandwich monotone, Decomposition by maxclique separators, Certifying algorithms, Practical and efficient circle graph recognition, Practical and efficient split decomposition via graph-labelled trees, Counting the number of independent sets in chordal graphs, Beyond classes of graphs with ``few minimal separators: FPT results through potential maximal cliques, Minimal obstructions for partial representations of interval graphs, Two methods for the generation of chordal graphs, A linear-time algorithm for proper interval graph recognition, A note on lexicographic breadth first search for chordal graphs, Clique coloring \(B_1\)-EPG graphs, A linear-time algorithm for clique-coloring problem in circular-arc graphs, Strict chordal and strict split digraphs, On the SPANNING \(k\)-TREE problem, On sequential heuristic methods for the maximum independent set problem, Extending partial representations of proper and unit interval graphs, End-vertices of LBFS of (AT-free) bigraphs, A new algorithm for decomposition of graphical models, Minimal proper interval completions, Treewidth computations. I: Upper bounds, Minimal split completions, The induced path function, monotonicity and betweenness, On end-vertices of lexicographic breadth first searches, Chordal deletion is fixed-parameter tractable, Fast minimal triangulation algorithm using minimum degree criterion, On listing, sampling, and counting the chordal graphs with edge constraints, Approximating maximum weight \(K\)-colorable subgraphs in chordal graphs, Enumeration of the perfect sequences of a chordal graph, Treewidth and minimum fill-in on permutation graphs in linear time, The isomorphism problem for \(k\)-trees is complete for logspace, An \(O(nm)\)-time certifying algorithm for recognizing HHD-free graphs, A direct active set algorithm for large sparse quadratic programs with simple bounds, The solution space of sorting with recurring comparison faults, On the complexity of the sandwich problems for strongly chordal graphs and chordal bipartite graphs, Single-edge monotonic sequences of graphs and linear-time algorithms for minimal completions and deletions, Algorithms for unipolar and generalized split graphs, Efficient algorithms for network localization using cores of underlying graphs, Maximum induced matchings for chordal graphs in linear time, On a property of minimal triangulations, Laminar structure of ptolemaic graphs with applications, Maximum induced matching problem on hhd-free graphs, Exploiting special structure in semidefinite programming: a survey of theory and applications, On 3-Steiner simplicial orderings, Domination, independent domination, and duality in strongly chordal graphs, Some aspects of perfect elimination orderings in chordal graphs, Calculs de complexité relatifs à une méthode de dissection emboîtée, Positive definite completions of partial Hermitian matrices, Decomposition by clique separators, Finding maximum cliques in arbitrary and in special graphs, Recognizing different types of beta-cycles in a database scheme, \(K_ i\)-covers. I: Complexity and polytopes, Hybrid backtracking bounded by tree-decomposition of constraint networks, On algorithms for (\(P_5\), gem)-free graphs, Perfect edge domination and efficient edge domination in graphs, On claw-free asteroidal triple-free graphs, Arboricity and bipartite subgraph listing algorithms, Generating and characterizing the perfect elimination orderings of a chordal graph, Efficient algorithms for minimum weighted colouring of some classes of perfect graphs, An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, New linear time algorithms for generating perfect elimination orderings of chordal graphs, Fixed-parameter tractability of graph modification problems for hereditary properties, Restricted triangulation on circulant graphs, \(r\)-dominating cliques in graphs with hypertree structure, Decomposition in multidimensional Boolean-optimization problems with sparse matrices, Separators and structure prediction in sparse orthogonal factorization, LexBFS-orderings and powers of chordal graphs, Method of fundamental solutions for 3D elasticity with body forces by coupling compactly supported radial basis functions, Cuts, matrix completions and graph rigidity, Graph extremities defined by search algorithms, An introduction to clique minimal separator decomposition, Computing a clique tree with the algorithm maximal label search, Weak bipolarizable graphs, Labeling algorithms for domination problems in sun-free chordal graphs, Algorithmic aspects of intersection graphs and representation hypergraphs, A polynomial algorithm for the parity path problem on perfectly orientable graphs, A note on odd/even cycles, Quasi-threshold graphs, The algorithmic use of hypertree structure and maximum neighbourhood orderings, Finding a sun in building-free graphs, Computation of the Shapley value of minimum cost spanning tree games: P-hardness and polynomial cases, On treewidth and minimum fill-in of asteroidal triple-free graphs, Separability generalizes Dirac's theorem, MPQ-trees for the orthogonal packing problem, On linear and circular structure of (claw, net)-free graphs, Interval degree and bandwidth of a graph, A simple algorithm to generate the minimal separators and the maximal cliques of a chordal graph, On symbolic factorization of partitioned sparse symmetric matrices, Maximum independent set and maximum clique algorithms for overlap graphs, On minimal augmentation of a graph to obtain an interval graph, Matrix completions and chordal graphs, Optimal packing and covering in the plane are NP-complete, The normal graph conjecture for two classes of sparse graphs, A decomposition algorithm for learning Bayesian networks based on scoring function, A new graph parameter to measure linearity, Solving problems on graphs of high rank-width, Some results on the target set selection problem, A fully dynamic graph algorithm for recognizing interval graphs, Hereditary dominating pair graphs, Strongly orderable graphs. A common generalization of strongly chordal and chordal bipartite graphs, LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem, An \(O(n^2)\) time algorithm for the minimal permutation completion problem, Independent domination in chordal graphs, Tractability of most probable explanations in multidimensional Bayesian network classifiers, Inheritance principles for chordal graphs, Some aspects of the semi-perfect elimination, A simple linear time algorithm for the locally connected spanning tree problem on maximal planar chordal graphs, \((i,j)\) competition graphs, Cycle-free partial orders and chordal comparability graphs, Finding large holes, An inertia formula for Hermitian matrices with sparse inverses, On the classes of interval graphs of limited nesting and count of lengths, Efficient enumeration of maximal \(k\)-degenerate induced subgraphs of a chordal graph, Maximum induced matching algorithms via vertex ordering characterizations, On distance-preserving elimination orderings in graphs: complexity and algorithms, Non-edge orientation and vertex ordering characterizations of some classes of bigraphs, Recognition and computation of minimal triangulations for AT-free claw-free and co-comparability graphs, Tree decompositions with small cost, On the structure of (\(P_{5}\),\,gem)-free graphs, Chordal co-gem-free and (\(P_{5}\),\,gem)-free graphs have bounded clique-width, An eccentricity 2-approximating spanning tree of a chordal graph is computable in linear time, Joint density of correlations in the correlation matrix with chordal sparsity patterns, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms, On \(k\)-tree containment graphs of paths in a tree, Subexponential parameterized algorithms and kernelization on almost chordal graphs, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Paired threshold graphs, A characterization of graphs with interval two-step graphs, Chromatic numbers of competition graphs, Representing triangulated graphs in stars, A chordal preconditioner for large-scale optimization, Recognition of some perfectly orderable graph classes, Exploiting variable sparsity in computing equilibria of biological dynamical systems by triangular decomposition, An optimal algorithm for solving the searchlight guarding problem on weighted interval graphs, Avoidable vertices and edges in graphs: existence, characterization, and applications, Minimal vertex separators of chordal graphs, On the semi-perfect elimination, On the consecutive ones property, Construction of a simple elimination scheme for a chordal comparability graph in linear time, A simple 3-sweep LBFS algorithm for the recognition of unit interval graphs, On the complexity of local-equitable coloring of graphs, Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing, Recognition of perfect elimination bipartite graphs, The forbidden subgraph characterization of directed vertex graphs, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs, A practical algorithm for making filled graphs minimal, Polynomial algorithms for the weighted perfect domination problems on chordal graphs and split graphs, On constructing the elimination tree, On cocolourings and cochromatic numbers of graphs, On vertex ranking of a starlike graph, The maximum clique problem, Recognition algorithm for intersection graphs of edge disjoint paths in a tree, An implementation of the iterative proportional fitting procedure by propagation trees., Medians in median graphs and their cube complexes in linear time, A fast direct solver for nonlocal operators in wavelet coordinates, Optimal decomposition by clique separators, A faster algorithm to recognize undirected path graphs, Recognizing graph search trees, Tree-decompositions with bags of small diameter, Reconstruction of line-embeddings of graphons, An \(O( n^{3})\)-time recognition algorithm for hhds-free graphs, Constant Time Enumeration by Amortization, How to use spanning trees to navigate in graphs, Model Rejection and Parameter Reduction via Time Series, Graphs with a unique maximum independent set up to automorphisms, Weighted 2-sections and hypergraph reconstruction, Sequential and parallel triangulating algorithms for elimination game and new insights on minimum degree, Well-partitioned chordal graphs, On Distance-d Independent Set and Other Problems in Graphs with “few” Minimal Separators, Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems, A local approach to concept generation, Linear-Time Algorithms for Finding Tucker Submatrices and Lekkerkerker--Boland Subgraphs, Isomorphism testing for \(T\)-graphs in FPT, On chordal and perfect plane near-triangulations, Graph searches and their end vertices, The referenced vertex ordering problem: theory, applications, and solution methods, Applying clique-decomposition for computing Gromov hyperbolicity, Polynomially bounding the number of minimal separators in graphs: reductions, sufficient conditions, and a dichotomy theorem, A faster diameter problem algorithm for a chordal graph, with a connection to its center problem, Perfect elimination orderings for symmetric matrices, Estimating the number of connected components in a graph via subgraph sampling, Extending partial representations of interval graphs, Vertex Ordering Characterizations of Graphs of Bounded Asteroidal Number, Recognizing Threshold Tolerance Graphs in $$O(n^2)$$ Time, Covering, Packing and Generalized Perfection, End-Vertices of Graph Search Algorithms, On some graph classes related to perfect graphs: a survey, Space-efficient algorithms for maximum cardinality search, its applications, and variants of BFS, Characterising circular-arc contact \(B_0\)-VPG graphs, Efficient isomorphism for \(S_d\)-graphs and \(T\)-graphs, Extendable shellability for \(d\)-dimensional complexes on \(d+3\) vertices, A Characterisation of the Minimal Triangulations of Permutation Graphs, Recognition of Polygon-Circle Graphs and Graphs of Interval Filaments Is NP-Complete, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Finding induced paths of given parity in claw-free graphs, Chordal graphs in triangular decomposition in top-down style, On the complexity of recognizing Stick, BipHook and max point-tolerance graphs, Classes of perfect graphs, Decremental optimization of vertex-coloring under the reconfiguration framework, Computing the hull number in \(\Delta \)-convexity, Improved Bounds for Poset Sorting in the Forbidden-Comparison Regime, Algorithms for convex hull finding in undirected graphical models, Two optimal strategies for active learning of causal models from interventional data, Bayesian graph selection consistency under model misspecification, Computing square roots of trivially perfect and threshold graphs, Moplex orderings generated by the LexDFs algorithm, Hardness and algorithms of equitable tree-coloring problem in chordal graphs, Searching for better fill-in, Burning Two Worlds, Decomposition of structural learning about directed acyclic graphs, Algorithms for generating strongly chordal graphs, End vertices of graph searches on bipartite graphs, Fast Constrained Image Segmentation Using Optimal Spanning Trees, Recognizing Sparse Perfect Elimination Bipartite Graphs, Minimal comparability completions of arbitrary graphs, On the strong chromatic index and maximum induced matching of tree-cographs, permutation graphs and chordal bipartite graphs, Tree decomposition and discrete optimization problems: a survey, Partial characterizations of clique-perfect graphs I: Subclasses of claw-free graphs, Minimum fill-in of sparse graphs: kernelization and approximation, Generalized domination in closure systems, Subclasses of \(k\)-trees: characterization and recognition, Ninth and tenth order virial coefficients for hard spheres in \(D\) dimensions, Simple algorithms for minimal triangulation of a graph and backward selection of a decomposable Markov network, Sparse matrix factor modification in structural reanalysis, A Separator Theorem for Chordal Graphs, Maximal sub-triangulation in pre-processing phylogenetic data, Proper Interval Vertex Deletion, Robustness to Dependency in Portfolio Optimization Using Overlapping Marginals, On the Power of Graph Searching for Cocomparability Graphs, Vertex elimination orderings for hereditary graph classes, On extremal sizes of locally k-tree graphs, The Solution Space of Sorting with Recurring Comparison Faults, An $$\mathcal {O}(n^2)$$ Time Algorithm for the Minimal Permutation Completion Problem, Convex dominating sets in maximal outerplanar graphs, Learning tractable Bayesian networks in the space of elimination orders, On some simplicial elimination schemes for chordal graphs, Decomposable Probabilistic Influence Diagrams, Inductive \(k\)-independent graphs and \(c\)-colorable subgraphs in scheduling: a review, Bayesian networks: the minimal triangulations of a graph, Some results on the Gaussian Markov random field construction problem based on the use of invariant subgraphs, One-way and round-trip center location problems, Lexicographic Orientation Algorithms, Convex geometries over induced paths with bounded length, Efficiently decomposing, recognizing and triangulating hole-free graphs without diamonds, Extending the MAX algorithm for maximum independent set, Extending partial representations of subclasses of chordal graphs, Modifying a graph using vertex elimination, New sufficient conditions for \(\alpha\)-redundant vertices, Coloring Meyniel graphs in linear time, Simple vertex ordering characterizations for graph search, Linear-time algorithms for tree root problems, A faster algorithm to recognize even-hole-free graphs, Speeding-up structured probabilistic inference using pattern mining
