×

On a graph partition problem with application to VLSI layout. (English) Zbl 0764.68132

Summary: We discuss a graph partition problem with application to VLSI layout. It is not difficult to show that the general partition problem is NP- complete, so we restrict our attention to some special classes of graphs. A graph is called a circle graph if the nodes of the graph represent the chords of a circle and there is an edge between the two nodes if the corresponding chords intersects. K. J. Supowit [IEEE Trans. Computer Aided Design 6, 93-94 (1987)] had posed the partition problem of circle graphs as an open problem. However, it is also not too difficult to show that the partition problem on circle graphs remains NP-complete. We give an integer linear programming formulation for the general graph partition problem. The problem can then be solved using one of the several techniques for solving integer linear programming problems. We show that the partition problem can be solved in polynomial time if the graph is a tree. A graph is called perfect if the graph and each of its induced subgraphs have chromatic numbers equal to the maximum cardinality of its cliques. When the partition problem is restricted to perfect graphs we observe an interesting phenomenon. In the integer linear programming formulation of the partition problem we always obtain an integral solution when the graph is perfect. This phenomenon is unusual because the constraint matrix does not belong to the class of totally unimodular, balanced, or perfect matrices [M. W. Padberg, Math. Program. 6, 180-196 (1974; Zbl 0284.90061)], for which such a phenomenon is guaranteed. In our extensive experimentation we always found an optimal integral solution when the graph is perfect. We conjecture that an optimal integral solution for the perfect graph always exists. If the conjecture is true then it is likely to lead to the development of a polynomial time algorithm for some subclasses of perfect graphs, such as the interval graphs. We show that for some other subclasses of perfect graphs, such as the permutation graphs, the number of maximal cliques may be exponentially large and as such, even if the conjecture is true, may not lead to a polynomial time algorithm for the partition problem. The partition problem is the generalization of the chromatic sum problem introduced by E. Kubicka and A. Schwenk in [Introduction to chromatic sums, Proc. ACM Computer Science Conf. (1989)]. The problem was referred to as weighted coloring problem by K. J. Supowit. However, L. Lovasz in [M. Groetschel, L. Lovasz and A. Schrijver, Geometric algorithms and combinatorial optimization (1988; Zbl 0634.05001)] uses weighted coloring problem to describe a different problem. To avoid confusion we refer to it as optimum cost chromatic partition (OCCP) problem. The problem is the following: Given a graph \(G=(V,E)\) and a cost vector \(C=\langle C_ 1,C_ 2,\dots,C_ n\rangle (| V|=n)\), partition the vertex set \(V\) into independent sets \(V_ 1,V_ 2,\dots,V_ k\), \(1\leq k\leq n\), such that \(\sum^ k_{i=1}C_ i| V_ i|\) is minimum. If we set cost \(C_ i=i\), then this problem reduces to the chromatic sum problem of E. Kubicka and A. Schwenk [Introduction to chromatic sums, Proc. ACM Computer Science Conf. (1989)].

MSC:

68R10 Graph theory (including graph drawing) in computer science
05C15 Coloring of graphs and hypergraphs
94C15 Applications of graph theory to circuits and networks
90C10 Integer programming
94C99 Circuits, networks
68R05 Combinatorics in computer science
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] Buckingham, M.A., Circle graphs, Courant computer science rept. no. 21, (1980)
[2] Chvatal, V., On certain polytopes associated with graphs, J. combin. theory ser. B, 18, 138-154, (1975) · Zbl 0277.05139
[3] Even, S.; Pnueli, A.; Lempel, A., Permutation graphs and transitive graphs, J. ACM., 19, 400-410, (1972) · Zbl 0251.05113
[4] Garey, M.R.; Johnson, D.S., Computers and intractability, (1979), Freeman New York · Zbl 0411.68039
[5] Gavril, F., Algorithms for a maximum clique and a maximum independent set of a circle graph, Networks, 3, 261-273, (1973) · Zbl 0259.05125
[6] Golumbic, M.C., Algorithmic graph theory and perfect graphs, (1980), Academic Press New York · Zbl 0541.05054
[7] Grotschel, M.; Lovasz, L.; Schrijver, A., Geometric algorithms and combinatorial optimization, (1988), Springer Berlin · Zbl 0634.05001
[8] Harary, F., Graph theory, (1972), Addison-Wesley Reading, MA · Zbl 0797.05064
[9] Hsu, C.P., Signal routing in integrated circuit layout, (1986), UMI Research Press
[10] Johnson, D.S., The NP-completeness column: an going guide, J. algorithms, 6, 434-451, (1985) · Zbl 0608.68032
[11] Karmarkar, N., A new polynomial time algorithm for linear programming, Combinatorica, 4, 373-395, (1984) · Zbl 0557.90065
[12] Khachiyan, L.G., A polynomial algorithm in linear programming, Soviet math. dokl., 20, 191-194, (1979) · Zbl 0414.90086
[13] Kim, H., Finding a maximum independent set in a permutation graph, Inform. process. lett., 36, 19-23, (1990) · Zbl 0703.68062
[14] Kubicka, E.; Schwenk, A., Introduction to chromatic sums, Proc. ACM computer science conf., (1989)
[15] Padberg, M.W., Perfect zero-one matrices, Math. programming, 6, 180-196, (1974) · Zbl 0284.90061
[16] Pinter, R.Y., River routing: methodology and analysis, ()
[17] Supowit, K.J., Finding a maximum planar subset of a set of nets in a channel, IEEE trans. computer aided design, 6, 93-94, (1987)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.