| Publication Title: |
A Dynamic Data Structure for Checking Hyperacyclicity |
| Publication Author: |
Liang, Percy |
| Additional Authors: |
Nati Srebro |
| LCS Document Number: |
MIT-LCS-TR-977 |
| Publication Date: |
1-3-2005 |
| LCS Group: |
Algorithms |
| Additional URL: |
|
| Abstract: |
| We present a dynamic data structure that keeps track of an acyclic hypergraph (equivalently, a triangulated graph) and enables verifying that adding a candidate hyperedge (clique) will not break the acyclicity of the augmented hypergraph. This is a generalization of the use of Tarjan's Union-Find data structure for maintaining acyclicity when augmenting forests, and the amortized time per operation has a similar almost-constant dependence on the size of the hypergraph. Such a data structure is useful when augmenting acyclic hypergraphs, e.g.\~in order to greedily construct a high-weight acyclic hypergraph. In designing this data structure, we introduce a hierarchical decomposition of acyclic hypergraphs that aid in understanding {\em hyper-connectivity}, and introduce a novel concept of a {\em hypercycle} which is excluded from acyclic hypergraphs. |
| To obtain this publication: |
|
|
|
To purchase a printed copy of this publication please contact
MIT
Document Services.
|