Counting clique trees and computing perfect elimination schemes in parallel
From MaRDI portal
DOI10.1016/0020-0190(89)90070-7zbMATH Open0685.68050OpenAlexW2110287499MaRDI QIDQ1262131FDOQ1262131
Authors: Chin-Wen Ho, R. C. T. 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
Recommendations
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Fast Parallel Algorithms for Chordal Graphs
- Efficient Parallel Algorithms for Chordal Graphs
- Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
- Sequential and parallel algorithms on compactly represented chordal and strongly chordal graphs
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Cites Work
- Intersection graphs of paths in a tree
- Incidence matrices and interval graphs
- On rigid circuit graphs
- The intersection graphs of subtrees in trees are exactly the chordal graphs
- Representation of a finite graph by a set of intervals on the real line
- The Round-Trip p-Center and Covering Problem on a Tree
- Triangulated graphs and the elimination process
- On the Desirability of Acyclic Database Schemes
- Finding a Maximum Clique in an Arbitrary Graph
- Tight Comparison Bounds on the Complexity of Parallel Sorting
- Title not available (Why is that?)
- A Separator Theorem for Chordal Graphs
- A characterisation of rigid circuit graphs
- An O(logn) parallel connectivity algorithm
- Tight Bounds on the Complexity of Parallel Sorting
- Deterministic coin tossing with applications to optimal parallel list ranking
- The edge inducibility of graphs
- Covering, Packing and Generalized Perfection
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Fast Parallel Algorithms for Chordal Graphs
Cited In (38)
- A new characterization of \(k\)-trees and some applications
- On the size of minimal separators for treedepth decomposition
- Separator orders in interval, cocomparability, and AT-free graphs
- Tree decomposition and discrete optimization problems: a survey
- The parallel complexity of elimination ordering procedures
- Linear-time algorithms for tree root problems
- One-phase algorithm for the determination of minimal vertex separators of chordal graphs
- Characterizing and computing the structure of clique intersections in strongly chordal graphs
- Subgraph trees in graph theory
- A vertex incremental approach for maintaining chordality
- Notes on the Distributed Computation of Merge Trees on CW-Complexes
- Searching for better fill-in
- Treewidth computation and extremal combinatorics
- Dynamic programming and planarity: improved tree-decomposition based algorithms
- Clique trees of infinite locally finite chordal graphs
- Computing the clique-separator graph for an interval graph in linear time
- A parallel algorithm for generating bicompatible elimination orderings of proper interval graphs
- A simple algorithm to find Hamiltonian cycles in proper interval graphs
- Minimal triangulations of graphs: a survey
- The 3-Steiner Root Problem
- Multigraph representations of hierarchical loglinear models
- The complexity of subtree intersection representation of chordal graphs and linear time chordal graph generation
- An efficient representation of chordal graphs
- The clique-separator graph for chordal graphs
- Efficient parallel algorithms for finding maximal cliques, clique trees, and minimum coloring on chordal graphs
- Minimum average distance clique trees
- Finding minimum height elimination trees for interval graphs in polynomial time
- A clique tree algorithm for partitioning a chordal graph into transitive subgraphs
- Parallel computation of perfect elimination schemes using partition techniques on triangulated graphs
- How to Use Planarity Efficiently: New Tree-Decomposition Based Algorithms
- A fully dynamic graph algorithm for recognizing interval graphs
- Clique tree generalization and new subclasses of chordal graphs
- Graphs that have separator tree representations
- Enumeration of Perfect Sequences of Chordal Graph
- Finding a maximum-weight convex set in a chordal graph
- MAT-free graphic arrangements and a characterization of strongly chordal graphs by edge-labeling
- Minimum Fill-In and Treewidth of Split+ ke and Split+ kv Graphs
- Minimum fill-in and treewidth of split \(+ ke\) and split \(+kv\) graphs
This page was built for publication: Counting clique trees and computing perfect elimination schemes in parallel
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1262131)
