Counting clique trees and computing perfect elimination schemes in parallel
From MaRDI portal
Publication:1262131
DOI10.1016/0020-0190(89)90070-7zbMath0685.68050OpenAlexW2110287499MaRDI QIDQ1262131
Chin-Wen Ho, Richard Chia-Tung Lee
Publication date: 1989
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(89)90070-7
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
Minimal triangulations of graphs: a survey, A vertex incremental approach for maintaining chordality, Computing the clique-separator graph for an interval graph in linear time, Finding minimum height elimination trees for interval graphs in polynomial time, Clique tree generalization and new subclasses of chordal graphs, A clique tree algorithm for partitioning a chordal graph into transitive subgraphs, Treewidth computation and extremal combinatorics, Towards a characterization of leaf powers by clique arrangements, Multigraph representations of hierarchical loglinear models, Minimum Average Distance Clique Trees, MAT-free graphic arrangements and a characterization of strongly chordal graphs by edge-labeling, The 3-Steiner Root Problem, How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms, Unnamed Item, Subgraph trees in graph theory, A fully dynamic graph algorithm for recognizing interval graphs, An efficient representation of chordal graphs, Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs, Searching for better fill-in, Characterizing and computing the structure of clique intersections in strongly chordal graphs, One-phase algorithm for the determination of minimal vertex separators of chordal graphs, Clique trees of infinite locally finite chordal graphs, Tree decomposition and discrete optimization problems: a survey, Separator orders in interval, cocomparability, and AT-free graphs, Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs, Dynamic programming and planarity: improved tree-decomposition based algorithms, The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation, A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs, A simple algorithm to find Hamiltonian cycles in proper interval graphs, On the computational complexity of vertex integrity and component order connectivity, The clique-separator graph for chordal graphs, Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs, Finding a Maximum-Weight Convex Set in a Chordal Graph, Linear-time algorithms for tree root problems
Cites Work
- Unnamed Item
- On rigid circuit graphs
- Intersection graphs of paths in a tree
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- A characterisation of rigid circuit graphs
- Incidence matrices and interval graphs
- Triangulated graphs and the elimination process
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- On the Desirability of Acyclic Database Schemes
- Tight Bounds on the Complexity of Parallel Sorting
- Covering, Packing and Generalized Perfection
- Representation of a finite graph by a set of intervals on the real line
- A Separator Theorem for Chordal Graphs
- Finding a Maximum Clique in an Arbitrary Graph
- The Round-Trip p-Center and Covering Problem on a Tree
- Deterministic coin tossing with applications to optimal parallel list ranking
- Tight Comparison Bounds on the Complexity of Parallel Sorting
- Fast Parallel Algorithms for Chordal Graphs
- The edge inducibility of graphs
- An O(logn) parallel connectivity algorithm
