Quotient Tree Partitioning of Undirected Graphs
The partitioning of the vertices of an undirected graph, in a way that makes its quotient graph a tree, mirrors a way of permuting a square symmetric matrix to allow its factoring with little fil-in. We analyze the complexity of finding the best partitioning and show that it is NP-complete. We also give a new and simpler implementation of an algorithm that finds a maximal quotient tree.
computer science; technical report
Previously Published As