Trapezoid graphs and their coloring
作者： Ido Dagan , Martin Charles Golumbic , Ron Yair Pinter
DOI: 10.1016/0166-218X(88)90032-7
关键词:
摘要: Abstract We define trapezoid graphs, an extension of both interval and permutation graphs. show that this new class properly contains the union two former classes, graphs are equivalent to incomparability partially ordered sets having order dimension at most two. provide optimal coloring algorithm for runs in time O(nk), where n is number nodes k chromatic graph. Our has direct applications channel routing on integrated circuits.
acm.org
elsevier.com
sci-hub.se 参考文章(11)
Douglas B. West, Parameters of Partial Orders and Graphs: Packing, Covering, and Representation Springer, Dordrecht. pp. 267- 350 ,(1985) , 10.1007/978-94-009-5315-4_8
Ron Y. Pinter, River Routing: Methodology and Analysis Springer, Berlin, Heidelberg. pp. 141- 163 ,(1983) , 10.1007/978-3-642-95432-0_9
Martin Charles Golumbic, Algorithmic aspects of intersection graphs and representation hypergraphs Graphs and Combinatorics. ,vol. 4, pp. 307- 321 ,(1988) , 10.1007/BF01864170
S. Even, A. Pnueli, A. Lempel, Permutation Graphs and Transitive Graphs Journal of the ACM. ,vol. 19, pp. 400- 410 ,(1972) , 10.1145/321707.321710
Mihalis Yannakakis, The Complexity of the Partial Order Dimension Problem Siam Journal on Algebraic and Discrete Methods. ,vol. 3, pp. 351- 358 ,(1982) , 10.1137/0603036
Martin Charles Golumbic, Doron Rotem, Jorge Urrutia, Comparability graphs and intersection graphs Discrete Mathematics. ,vol. 43, pp. 37- 46 ,(1983) , 10.1016/0012-365X(83)90019-5
Martin Charles Golumbic, Algorithmic graph theory and perfect graphs ,(1980)
David S Johnson, The NP-completeness column: An ongoing guide Journal of Algorithms. ,vol. 7, pp. 584- 601 ,(1986) , 10.1016/0196-6774(86)90020-9
Charles E. Leiserson, Ron Y. Pinter, Optimal Placement for River Routing VLSI Systems and Computations. ,vol. 12, pp. 126- 142 ,(1981) , 10.1007/978-3-642-68402-9_16
R. Y. Pinter, THE IMPACT OF LAYER ASSIGNMENT METHODS ON LAYOUT ALGORITHM FOR INTEGRATED CIRCUITS Massachusetts Institute of Technology. ,(1983)