{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2023,1,19]],"date-time":"2023-01-19T03:50:13Z","timestamp":1674100213767},"reference-count":27,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[1993,1,1]],"date-time":"1993-01-01T00:00:00Z","timestamp":725846400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Algorithmica"],"published-print":{"date-parts":[[1993,1]]},"DOI":"10.1007\/bf01185340","type":"journal-article","created":{"date-parts":[[2005,2,18]],"date-time":"2005-02-18T16:45:05Z","timestamp":1108745105000},"page":"84-100","source":"Crossref","is-referenced-by-count":11,"title":["Maximumk-covering of weighted transitive graphs with applications"],"prefix":"10.1007","volume":"9","author":[{"given":"M.","family":"Sarrafzadeh","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"R. D.","family":"Lou","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","reference":[{"key":"CR1","volume-title":"The Design and Analysis of Computer Algorithms","author":"A. V. Aho","year":"1974","unstructured":"Aho, A. V., Hopcroft, J. E., and Ullman, J. D.,The Design and Analysis of Computer Algorithms, Addison-Wesley, Reading, MA, 1974."},{"issue":"No. 2","key":"CR2","doi-asserted-by":"crossref","first-page":"221","DOI":"10.1007\/BF01553888","volume":"4","author":"M. J. Atallah","year":"1989","unstructured":"Atallah, M. J., and Kosaraju, S. R., An Efficient Algorithm for Maxdominance, with Applications,Algorithmica, Vol. 4, No. 2, 1989, pp. 221?236.","journal-title":"Algorithmica"},{"key":"CR3","unstructured":"Cong, J., and Liu, C. L., On the k-Layer Planar Subset and Via Minimization Problems, manuscript, University of Illinois at Urbana, 1989. Also appeared inProceedings of the 1990 European Design Automation Conference."},{"key":"CR4","doi-asserted-by":"crossref","first-page":"248","DOI":"10.1145\/321694.321699","volume":"19","author":"J. Edmonds","year":"1972","unstructured":"Edmonds, J., and Karp, R. M., Theoretical Improvements in Algorithmic Efficiency for Network Flow Problems,Journal of the ACM, Vol. 19, 1972, pp. 248?264.","journal-title":"Journal of the ACM"},{"key":"CR5","doi-asserted-by":"crossref","unstructured":"Gao, S., and Kaufmann, M., Channel Routing of Multiterminal Nets,Proceedings of the Symposium on Foundations of Computer Science, October 1987, pp. 316?325.","DOI":"10.1109\/SFCS.1987.13"},{"key":"CR6","volume-title":"Computers and Intractability","author":"M. R. Garey","year":"1979","unstructured":"Garey, M. R., and Johnson, D. S.,Computers and Intractability, Freeman, San Fransisco, 1979."},{"key":"CR7","doi-asserted-by":"crossref","first-page":"465","DOI":"10.1002\/net.3230170407","volume":"17","author":"F. Gavril","year":"1987","unstructured":"Gavril, F., Algorithms for Maximum k-Colorings and k-Coverings of Transitive Graphs,Networks, Vol. 17, 1987, pp. 465?470.","journal-title":"Networks"},{"key":"CR8","volume-title":"Algorithmic Graph Theory and Perfect Graphs","author":"M. G. Golumbic","year":"1980","unstructured":"Golumbic, M. G.,Algorithmic Graph Theory and Perfect Graphs, Academic Press, New York, 1980."},{"key":"CR9","doi-asserted-by":"crossref","unstructured":"Gupta, U., Lee, D. T., and Leung, J., An Optimal Solution for the Channel Assignment Problem,IEEE Transactions on Computers, November 1979, pp. 807?810.","DOI":"10.1109\/TC.1979.1675260"},{"key":"CR10","doi-asserted-by":"crossref","first-page":"459","DOI":"10.1002\/net.3230120410","volume":"12","author":"U. Gupta","year":"1982","unstructured":"Gupta, U., Lee, D. T., and Leung, J., Efficient Algorithms for Interval Graphs and Circular-Arc Graphs,Networks, Vol. 12, 1982, pp. 459?467.","journal-title":"Networks"},{"key":"CR11","unstructured":"Hsu, W. L., and Tsai, K. H., A Linear Time Algorithm for the Two Track Assignment Problem,Proceedings of the 1989 Allerton Conference, pp. 291?300."},{"issue":"No. 5","key":"CR12","doi-asserted-by":"crossref","first-page":"350","DOI":"10.1145\/359581.359603","volume":"20","author":"J. W. Hunt","year":"1977","unstructured":"Hunt, J. W., and Szymanski, T. G., A Fast Algorithm for Computing Longest Common Subsequence,Communications of the ACM, Vol. 20, No. 5, 1977, pp. 350?353.","journal-title":"Communications of the ACM"},{"issue":"No. 1","key":"CR13","doi-asserted-by":"crossref","first-page":"19","DOI":"10.1016\/S0167-9260(05)80033-1","volume":"10","author":"K. F. Liao","year":"1990","unstructured":"Liao, K. F., Lee, D. T., and Sarrafzadeh, M., Planar Subset of Multi-Terminal Nets,INTEGRATION: The VLSI Journal, Vol. 10, No. 1, 1990, pp. 19?37.","journal-title":"INTEGRATION: The VLSI Journal"},{"key":"CR14","doi-asserted-by":"crossref","unstructured":"Lou, R. D., Liao, F. K., and Sarrafzadeh, M., Planar Routing Around a Rectangle, to appear inJournal of Circuits, Systems, and Computers, 1992.","DOI":"10.1142\/S0218126692000039"},{"key":"CR15","doi-asserted-by":"crossref","unstructured":"Lou, R. D., and Sarrafzadeh, M., Circular Permutation Graph Family,Proceedings of the International Workshop on Discrete Algorithms and Complexity, Fukuoka, Japan, November 1989. To appear inDiscrete Applied Mathematics, 1992.","DOI":"10.1016\/0166-218X(92)90012-Y"},{"issue":"No. 2","key":"CR16","doi-asserted-by":"crossref","first-page":"285","DOI":"10.1137\/0405022","volume":"5","author":"R. D. Lou","year":"1990","unstructured":"Lou, R. D., Sarrafzadeh, M., and Lee, D. T., An Optimal Algorithm for the Maximum Two-Chain Problem,Proceedings of the First SIAM-ACM Conference on Discrete Algorithms, San Francisco, CA, January 1990. Also inSI AM Journal on Discrete Mathematics, Vol. 5, No. 2, pp. 285?304.","journal-title":"SI AM Journal on Discrete Mathematics"},{"issue":"No. 3","key":"CR17","doi-asserted-by":"crossref","first-page":"184","DOI":"10.1109\/TCAD.1984.1270074","volume":"3","author":"M. Marek-Sadowska","year":"1984","unstructured":"Marek-Sadowska, M., An Unconstraint Topological Via Minimization,IEEE Transactions on Computer-Aided Design, Vol. 3, No. 3, July 1984, pp. 184?190.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"issue":"No. 2","key":"CR18","doi-asserted-by":"crossref","first-page":"213","DOI":"10.1007\/BF01840443","volume":"1","author":"K. Mehlhorn","year":"1986","unstructured":"Mehlhorn, K., Preparata, F. P., and Sarrafzadeh, M., Channel Routing in Knock-Knee Mode: Simplified Algorithms and Proofs,Algorithmica, Vol. 1, No. 2, October 1986, pp. 213?221.","journal-title":"Algorithmica"},{"key":"CR19","volume-title":"Layout Design and Verification","author":"T. Ohtsuki","year":"1986","unstructured":"Ohtsuki, T.,Layout Design and Verification, Elsevier, Amsterdam, 1986."},{"issue":"No. 5","key":"CR20","doi-asserted-by":"crossref","first-page":"427","DOI":"10.1109\/TC.1984.1676459","volume":"33","author":"F. P. Preparata","year":"1984","unstructured":"Preparata, F. P., and Lipski, W., Optimal Three-Layer Channel Routing,IEEE Transaction on Computers, Vol. 33, No. 5, May 1984, pp. 427?437.","journal-title":"IEEE Transaction on Computers"},{"key":"CR21","first-page":"189","volume-title":"VLSI: Algorithms and Architectures","author":"F. P. Preparata","year":"1984","unstructured":"Preparata, F. P., and Sarrafzadeh, M., Channel Routing of Nets of Bounded Degree, inVLSI: Algorithms and Architectures (P. Bertolazzi and F. Luccio, ed.), North-Holland, Amsterdam, 1984, pp. 189?203."},{"key":"CR22","doi-asserted-by":"crossref","DOI":"10.1007\/978-1-4612-1098-6","volume-title":"Computational Geometry","author":"F. P. Preparata","year":"1985","unstructured":"Preparata, F. P., and Shamos, M. I.,Computational Geometry, Springer-Verlag, New York, 1985."},{"issue":"No. 11","key":"CR23","doi-asserted-by":"crossref","first-page":"1165","DOI":"10.1109\/43.41502","volume":"8","author":"C. S. Rim","year":"1989","unstructured":"Rim, C. S., Kashiwabara, T., and Nakajima, K., Exact Algorithms for Multilayer Topological Via Minimization,IEEE Transactions on Computer-Aided Design, Vol. 8, No. 11, November 1989, pp. 1165?1184.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"issue":"No. 3","key":"CR24","doi-asserted-by":"crossref","first-page":"658","DOI":"10.1137\/0214048","volume":"14","author":"J. Spinrad","year":"1985","unstructured":"Spinrad, J., On Comparability and Permutation Graphs,SIAM Journal on Computing, Vol. 14, No. 3, August 1985, pp. 658?670.","journal-title":"SIAM Journal on Computing"},{"issue":"No. 8","key":"CR25","doi-asserted-by":"crossref","first-page":"890","DOI":"10.1109\/43.31548","volume":"8","author":"M. Sarrafzadeh","year":"1989","unstructured":"Sarrafzadeh, M., and Lee, D. T., New Approach to Topological Via Minimization,IEEE Transactions on Computer-Aided Design, Vol. 8, No. 8, August 1989, pp. 890?900.","journal-title":"IEEE Transactions on Computer-Aided Design"},{"issue":"No. 11","key":"CR26","doi-asserted-by":"crossref","first-page":"1307","DOI":"10.1109\/12.102839","volume":"40","author":"M. Sarrafzadeh","year":"1991","unstructured":"Sarrafzadeh, M., and Lee, D. T., Topological Via Minimization Revisited,IEEE Transactions on Computers, Vol. 40, No. 11, November 1991, pp. 1307?1312.","journal-title":"IEEE Transactions on Computers"},{"key":"CR27","doi-asserted-by":"crossref","unstructured":"Sarrafzadeh, M., and Preparata, F. P., Compact Channel Routing of Multiterminal Nets,Annals of Discrete Mathematics: Journal of Mathematics Studies, April 1985, pp. 255?279.","DOI":"10.1016\/S0304-0208(08)73111-6"}],"container-title":["Algorithmica"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185340.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/BF01185340\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/BF01185340","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,4,5]],"date-time":"2020-04-05T21:15:58Z","timestamp":1586121358000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/BF01185340"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1993,1]]},"references-count":27,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1993,1]]}},"alternative-id":["BF01185340"],"URL":"https:\/\/doi.org\/10.1007\/bf01185340","relation":{},"ISSN":["0178-4617","1432-0541"],"issn-type":[{"value":"0178-4617","type":"print"},{"value":"1432-0541","type":"electronic"}],"subject":[],"published":{"date-parts":[[1993,1]]}}}