A clique tree algorithm for partitioning a chordal graph into transitive subgraphs
| Autor: | Xiaoqing Yuan, Barry W. Peyton, Alex Pothen |
|---|---|
| Rok vydání: | 1995 |
| Předmět: |
Block graph
Discrete mathematics Numerical Analysis Clique-sum Algebra and Number Theory Interval graph 010103 numerical & computational mathematics 0102 computer and information sciences Clique graph 01 natural sciences Combinatorics Treewidth 010201 computation theory & mathematics Chordal graph Computer Science::Discrete Mathematics Discrete Mathematics and Combinatorics Split graph Geometry and Topology 0101 mathematics K-tree Algorithm Mathematics MathematicsofComputing_DISCRETEMATHEMATICS |
| Zdroj: | Linear Algebra and its Applications. :553-588 |
| ISSN: | 0024-3795 |
| DOI: | 10.1016/0024-3795(95)00092-6 |
| Popis: | A partitioning problem on chordal graphs that arises in the solution of sparse triangular systems of equations on parallel computers is considered. Roughly the problem is to partition a chordal graph G into the fewest transitively orientable subgraphs over all perfect elimination orderings of G, subject to a certain precedence relationship on its vertices. In earlier work, a greedy scheme that solved the problem by eliminating a largest subset of vertices at each step was described, and an algorithm implementing the scheme in time and space linear in the number of edges of the graph was provided. A more efficient greedy scheme, obtained by representing the chordal graph in terms of its maximal cliques, is described here. The new greedy scheme eliminates, in a specified order, a largest set of “persistent leaves,” a subset of the leaf cliques in the current graph, at each step. Several new results about minimal vertex separators in chordal graphs, and in particular, the concept of a critical separator of a leaf clique, are employed to prove that the new scheme solves the partitioning problem. We provide an algorithm implementing the scheme in time and space linear in the size of the clique tree. We anticipate that a critical separator of a leaf clique may be a useful concept in other problems on chordal graphs. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect