A Separator Theorem for Chordal Graphs
From MaRDI portal
Publication:3344230
DOI10.1137/0605032zbMath0551.05049OpenAlexW2017223622MaRDI QIDQ3344230
John R. Gilbert, Anders Edenbrandt, Donald J. Rose
Publication date: 1984
Published in: SIAM Journal on Algebraic Discrete Methods (Search for Journal in Brave)
Full work available at URL: https://hdl.handle.net/1813/6362
Related Items
An efficient parallel algorithm for the minimal elimination ordering (MEO) of an arbitrary graph, Collective tree spanners in graphs with bounded parameters, The analysis of a nested dissection algorithm, Largest chordal and interval subgraphs faster than \(2^n\), Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs, Approximation and Kernelization for Chordal Vertex Deletion, Space-efficient algorithms for reachability in directed geometric graphs, Bi-Covering: Covering Edges with Two Small Subsets of Vertices, Space efficient algorithm for solving reachability using tree decomposition and 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, An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs, Distributed Relationship Schemes for Trees, Anticoloring and separation of graphs, Collective additive tree spanners of bounded tree-breadth graphs with generalizations and consequences, Treewidth computations. I: Upper bounds, Collective Additive Tree Spanners of Homogeneously Orderable Graphs, Counting clique trees and computing perfect elimination schemes in parallel, An Approximation Algorithm for the Tree t-Spanner Problem on Unweighted Graphs via Generalized Chordal Graphs, A partial k-arboretum of graphs with bounded treewidth, Additive sparse spanners for graphs with bounded length of largest induced cycle
Cites Work
- Unnamed Item
- Unnamed Item
- On rigid circuit graphs
- On simple characterizations of k-trees
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- A separator theorem for graphs of bounded genus
- A Separator Theorem for Planar Graphs
- Generalized Nested Dissection
- Applications of a Planar Separator Theorem
- Computing the Minimum Fill-In is NP-Complete
- On the Problem of Partitioning Planar Graphs
- Algorithmic Aspects of Vertex Elimination on Graphs
- Area-efficient VLSI layouts for binary hypercubes
