Algorithmic Aspects of Vertex Elimination on Graphs
From MaRDI portal
Publication:4124209
DOI10.1137/0205021zbMath0353.65019DBLPjournals/siamcomp/RoseTL76OpenAlexW2086119402WikidataQ56016677 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 (only showing first 100 items - show all)
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
This page was built for publication: Algorithmic Aspects of Vertex Elimination on Graphs
