Optimizing IPOG's Vertical Growth with Constraints Based on Hypergraph Coloring

摘要: In this paper, we present an optimization of IPOG's vertical growth phase in the presence constraints. The problem is modeled as a classical NP-hard graph called "Minimum Vertex Coloring". model, vertices are either missing tuples that waiting to be colored or existing tests already different colors at initial state, edges/hyperedges conflicts among cannot put same test. After coloring, group color can transformed exactly valid Since original IPOG algorithm uses arbitrary order cover during growth, reduce number tests, compute Degree Conflicts (DOC) for each tuple, and non-increasing DOC. We implement new incorporating optimization. experimental results show reduces many real-life systems with