Circular permutation graph family with applications |
| |
Authors: | R D Lou and M Sarrafzadeh |
| |
Institution: | Department of Electrical Engineering and Computer Science, Northwestern University, Evanston, IL 60208, USA |
| |
Abstract: | In a circular permutation diagram, there are two sets of terminals on two concentric circles: Cin and Cout. Given a permutation Π = π1, π2, …, πn], terminal i on Cin and terminal πi on Cout are connected by a wire. The intersection graph Gc of a circular permutation diagram Dc is called a circular permutation graph of a permutation Π corresponding to the diagram Dc. The set of all circular permutation graphs of a permutation Π is called the circular permutation graph family of permutation Π. In this paper, we propose the following: (1) an O(V + E) time algorithm to check if a labeled graph G = (V, E) is a labeled circular permutation graph. (2) An O(n log n + nt) time algorithm to find a maximum independent set of a family, where n = Π and t is the cardinality of the output. (Number t in the worst case is O(n). However, if Π is uniformly distributed (and independent from i), its expected value is O(√n).) (3) An O(min(δVclog logVc,VclogVc) + Ec) time algorithm for finding a maximum independent set of a circular permutation diagram Dc, where δ is the minimum degree of vertices in the intersection graph Gc = (Vc,Ec) of Dc. (4) An O(n log log n) time algorithm for finding a maximum clique and the chromatic number of a circular permutation diagram, where n is the number of wires in the diagram. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|