Given a graph G with weighted edges,and a subset of nodes T,the T-join problem asks for a minimum weight edge set A such that a node u is incident to an odd number of edges of A iff u T.We describe the applications of the T-join problem in sparse graphs to the phase assignment progblem in VLSI mask layout and to conformal refinement of finite element meshes.We suggest a practical algorithm for the T-join problem.In sparse graphs,this algorithm is faster than previously known methods.Coputational experience with industrial VLSI layout benchmarks shows the advantages of the new algorithm.
展开▼
机译：给定具有权重边缘的图G和节点T的子集，T联接问题要求最小权重边缘集A使得节点u入射到A iff u T的奇数个边缘。稀疏图中的T-join问题在VLSI掩模布局中的相位分配问题以及有限元网格的共形精化中的应用。我们提出了一种实用的T-join问题算法。在稀疏图中，该算法比以前更快工业VLSI布局基准测试的经验证明了新算法的优势。
展开▼
