{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T05:41:13Z","timestamp":1737006073984,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":21,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540679011"},{"type":"electronic","value":"9783540446125"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2000]]},"DOI":"10.1007\/3-540-44612-5_12","type":"book-chapter","created":{"date-parts":[[2007,5,5]],"date-time":"2007-05-05T13:28:20Z","timestamp":1178371700000},"page":"162-171","source":"Crossref","is-referenced-by-count":1,"title":["Edge-Bisection of Chordal Rings"],"prefix":"10.1007","author":[{"given":"Lali","family":"Barri\u00e9re","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Josep","family":"F\u00e1brega","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2001,6,1]]},"reference":[{"issue":"4","key":"12_CR1","doi-asserted-by":"crossref","first-page":"398","DOI":"10.1109\/71.97897","volume":"2","author":"A. Agarwal","year":"1991","unstructured":"A. Agarwal. Limits on interconnection network performance. IEEE Transactions on Parallel and Distributed Systems, 2(4):398\u2013412, October 1991.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"12_CR2","doi-asserted-by":"publisher","first-page":"271","DOI":"10.1007\/BF01371728","volume":"26","author":"F. Annexstein","year":"1993","unstructured":"F. Annexstein and M. Baumslag. On the diameter and bisector size of Cayley graphs. Math. Systems Theory, 26:271\u2013291, 1993.","journal-title":"Math. Systems Theory"},{"issue":"4","key":"12_CR3","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1109\/TC.1981.1675777","volume":"C-30","author":"B. Arden","year":"1981","unstructured":"B. Arden and H. Lee. Analysis of chordal ring network. IEEE Trans. Comput., C-30(4):291\u2013295, April 1981.","journal-title":"IEEE Trans. Comput."},{"key":"12_CR4","doi-asserted-by":"crossref","unstructured":"S. Arora, D. Karger, and M. Karpinski. Polynomial time approximation schemes for dense instances of NP-hard problems. In Proceedings of the 27th Annual ACM Symposium on Theory of Computing (STOC-95), pages 284\u2013293. ACM Press, 1995.","DOI":"10.1145\/225058.225140"},{"key":"12_CR5","first-page":"17","volume":"5","author":"L. Barri\u00e9re","year":"1999","unstructured":"L. Barri\u00e9re. Triangulations and chordal rings. In 6th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO), volume 5 of Proceedings in Informatics, pages 17\u201331. Carleton Scientific, 1999.","journal-title":"6th Int. Colloquium on Structural Information and Communication Complexity (SIROCCO)"},{"key":"12_CR6","unstructured":"L. Barri\u00e9re, J. Cohen, and M. Mitjana. Gossiping in chordal rings under the line model. In J. Hromkovic and W. Unger, editors, Proceedings of the MFCS\u201998 Workshop on Communication, pages 37\u201347, 1998."},{"key":"12_CR7","doi-asserted-by":"crossref","first-page":"589","DOI":"10.1007\/BF01301966","volume":"29","author":"S. Blackburn","year":"1996","unstructured":"S. Blackburn. Node bisectors of Cayley graphs. Mathematical Systems Theory, 29:589\u2013598, 1996.","journal-title":"Mathematical Systems Theory"},{"key":"12_CR8","doi-asserted-by":"crossref","unstructured":"R. Boppana. Eigenvalues and graph bisection: An average-case analysis. In Ashok K. Chandra, editor, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, pages 280\u2013285, Los Angeles, CA, October 1987. IEEE Computer Society Press.","DOI":"10.1109\/SFCS.1987.22"},{"key":"12_CR9","doi-asserted-by":"crossref","unstructured":"T. Bui, S. Chaudhuri, T. Leighton, and M. Sipser. Graph bisection algorithms with good average case behavior. In 25th Annual Symposium on Foundations of Computer Science, pages 181\u2013192, Los Angeles, Ca., USA, October 1984. IEEE Computer Society Press.","DOI":"10.1109\/SFCS.1984.715914"},{"key":"12_CR10","doi-asserted-by":"crossref","unstructured":"D. Dolev, J. Halpern, B. Simons, and R. Strong. A new look at fault tolerant network routing. In Proc. ACM 16th STOC, pages 526\u2013535, 1984.","DOI":"10.1145\/800057.808723"},{"key":"12_CR11","doi-asserted-by":"crossref","first-page":"420","DOI":"10.1147\/rd.175.0420","volume":"17","author":"W. Donath","year":"1973","unstructured":"W. Donath and A. Hoffman. Lower bounds for the partitioning of graphs. IBM Journal of Research and Developement, 17:420\u2013425, 1973.","journal-title":"IBM Journal of Research and Developement"},{"issue":"4","key":"12_CR12","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1137\/0205048","volume":"5","author":"S. Even","year":"1976","unstructured":"S. Even, A. Itai, and A. Shamir. On the complexity of timetable and multicommodity flow problems. SIAM Journal of Computing, 5(4):691\u2013703, 1976.","journal-title":"SIAM Journal of Computing"},{"key":"12_CR13","unstructured":"N. Garey and D. Johnson. Computers and Intractability-A Guide to Theory of NP-completeness. W.H. Freeman and Company, 1979."},{"key":"12_CR14","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1002\/net.3230240204","volume":"24","author":"M.-C. Heydemann","year":"1994","unstructured":"M.-C. Heydemann, J.-C. Meyer, J. Opatrny, and D. Sotteau. Forwarding indices of consistent routings and their complexity. Networks, 24:75\u201382, 1994.","journal-title":"Networks"},{"key":"12_CR15","series-title":"Lect Notes Comput Sci","volume-title":"(SWAT\u201994)","author":"J. Hromkovic","year":"1994","unstructured":"J. Hromkovic, R. Klasing, W. Unger, and H. Wagener. Optimal algorithms for broadcast and gossip in edge-disjoint path modes. In (SWAT\u201994), Lecture Notes in Computer Science 824, 1994."},{"key":"12_CR16","doi-asserted-by":"crossref","first-page":"291","DOI":"10.1002\/j.1538-7305.1970.tb01770.x","volume":"49","author":"B. Kerninghan","year":"1970","unstructured":"B. Kerninghan and S. Lin. An efficient heuristic procedure for partitioning graphs. Bell Systems Technology Journal, 49:291\u2013307, 1970.","journal-title":"Bell Systems Technology Journal"},{"key":"12_CR17","doi-asserted-by":"crossref","unstructured":"F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees and Hypercubes. Morgan Kaufmann Publishers, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"12_CR18","unstructured":"R. Lipton and R. Tarjan. A separator theorem for planar graphs. In WATERLOO: Proceedings of a Conference on Theoretical Computer Science, 1977."},{"key":"12_CR19","doi-asserted-by":"crossref","unstructured":"Jerrum M and G. Sorkin. Simulated annealing for graph bisection. In 34th Annual Symposium on Foundations of Computer Science, pages 94\u2013103, Palo Alto, California, 3\u20135 November 1993. IEEE.","DOI":"10.1109\/SFCS.1993.366878"},{"key":"12_CR20","series-title":"PhD thesis","volume-title":"Grafos y digrafos asociados con teselaciones como modelos para redes de interconexi\u00f3n","author":"P. Morillo","year":"1987","unstructured":"P. Morillo. Grafos y digrafos asociados con teselaciones como modelos para redes de interconexi\u00f3n. PhD thesis, Universitat Polit\u00e9cnica de Catalunya, Barcelona, Spain, 1987."},{"key":"12_CR21","doi-asserted-by":"crossref","unstructured":"D. Robinson. A Course in Theory of Groups, volume 80 of Graduate Texts in Math. Springer, 1996.","DOI":"10.1007\/978-1-4419-8594-1"}],"container-title":["Lecture Notes in Computer Science","Mathematical Foundations of Computer Science 2000"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44612-5_12","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,16]],"date-time":"2025-01-16T02:16:00Z","timestamp":1736993760000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44612-5_12"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2000]]},"ISBN":["9783540679011","9783540446125"],"references-count":21,"URL":"https:\/\/doi.org\/10.1007\/3-540-44612-5_12","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2000]]}}}