{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,1,21]],"date-time":"2025-01-21T05:20:13Z","timestamp":1737436813588,"version":"3.33.0"},"publisher-location":"Berlin, Heidelberg","reference-count":46,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783540425007"},{"type":"electronic","value":"9783540446880"}],"license":[{"start":{"date-parts":[[2001,1,1]],"date-time":"2001-01-01T00:00:00Z","timestamp":978307200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2001]]},"DOI":"10.1007\/3-540-44688-5_11","type":"book-chapter","created":{"date-parts":[[2007,8,28]],"date-time":"2007-08-28T13:43:33Z","timestamp":1188308613000},"page":"129-144","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Using PRAM Algorithms on a Uniform-Memory-Access Shared-Memory Architecture"],"prefix":"10.1007","author":[{"given":"David A.","family":"Bader","sequence":"first","affiliation":[]},{"given":"Ajith K.","family":"Illendula","sequence":"additional","affiliation":[]},{"given":"Bernard M. E.","family":"Moret","sequence":"additional","affiliation":[]},{"given":"Nina R.","family":"Weisse-Bernstein","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2001,8,17]]},"reference":[{"key":"11_CR1","doi-asserted-by":"crossref","unstructured":"A. Aggarwal, B. Alpern, A. Chandra, and M. Snir. A Model for Hierarchical Memory. In Proceedings of the 19th Annual ACM Symposium of Theory of Computing (STOC), pages 305\u2013314, New York City, May 1987.","DOI":"10.1145\/28395.28428"},{"key":"11_CR2","doi-asserted-by":"publisher","first-page":"1116","DOI":"10.1145\/48529.48535","volume":"31","author":"A. Aggarwal","year":"1988","unstructured":"A. Aggarwal and J. Vitter. The Input\/Output Complexity of Sorting and Related Problems. Communications of the ACM, 31:1116\u20131127, 1988.","journal-title":"Communications of the ACM"},{"key":"11_CR3","doi-asserted-by":"publisher","first-page":"72","DOI":"10.1007\/BF01185206","volume":"12","author":"B. Alpern","year":"1994","unstructured":"B. Alpern, L. Carter, E. Feig, and T. Selker. The Uniform Memory Hierarchy Model of Computation. Algorithmica, 12:72\u2013109, 1994.","journal-title":"Algorithmica"},{"key":"11_CR4","doi-asserted-by":"crossref","unstructured":"N. M. Amato, J. Perdue, A. Pietracaprina, G. Pucci, and M. Mathis. Predicting performance on SMPs. a case study: The SGI Power Challenge. In Proceedings of the International Parallel and Distributed Processing Symposium (IPDPS 2000), pages 729\u2013737, Cancun, Mexico, May 2000.","DOI":"10.1109\/IPDPS.2000.846058"},{"issue":"1","key":"11_CR5","doi-asserted-by":"publisher","first-page":"92","DOI":"10.1006\/jpdc.1999.1541","volume":"58","author":"D. A. Bader","year":"1999","unstructured":"D. A. Bader and J. J\u00e1J\u00e1. SIMPLE: A Methodology for Programming High Performance Algorithms on Clusters of Symmetric Multiprocessors (SMPs). Journal of Parallel and Distributed Computing, 58(1):92\u2013108, 1999.","journal-title":"Journal of Parallel and Distributed Computing"},{"issue":"9","key":"11_CR6","doi-asserted-by":"publisher","first-page":"943","DOI":"10.1109\/71.615440","volume":"8","author":"G. E. Blelloch","year":"1997","unstructured":"G. E. Blelloch, P. B. Gibbons, Y. Matias, and M. Zagha. Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors. IEEE Transactions on Parallel and Distributed Systems, 8(9):943\u2013958, 1997.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"issue":"2","key":"11_CR7","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/s004930050051","volume":"19","author":"M. H. Carvalho","year":"1999","unstructured":"M. H. Carvalho, C. L. Lucchesi, and U. S. R. Murty. Ear Decompositions of Matching Covered Graphs. Combinatorica, 19(2):151\u2013174, 1999.","journal-title":"Combinatorica"},{"issue":"1","key":"11_CR8","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1109\/40.653032","volume":"18","author":"A. Charlesworth","year":"1998","unstructured":"A. Charlesworth. Starfire: extending the SMP envelope. IEEE Micro, 18(1):39\u201349, 1998.","journal-title":"IEEE Micro"},{"issue":"2","key":"11_CR9","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1137\/S0895480196304234","volume":"12","author":"J. Chen","year":"1999","unstructured":"J. Chen and S. P. Kanchi. Graph Ear Decompositions and Graph Embeddings. SI AM Journal on Discrete Mathematics, 12(2):229\u2013242, 1999.","journal-title":"SI AM Journal on Discrete Mathematics"},{"key":"11_CR10","unstructured":"P. Crescenzi, C. Demetrescu, I. Finocchi, and R. Petreschi. LEONARDO: A Software Visualization System. In Proceedings of the First Workshop on Algorithm Engineering (WAE\u201997), pages 146\u2013155, Venice, Italy, sep 1997."},{"key":"11_CR11","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0890-5401(92)90041-D","volume":"98","author":"D. Eppstein","year":"1992","unstructured":"D. Eppstein. Parallel Recognition of Series Parallel Graphs. Information & Computation, 98:41\u201355, 1992.","journal-title":"Information & Computation"},{"issue":"3","key":"11_CR12","doi-asserted-by":"publisher","first-page":"388","DOI":"10.1137\/S0895480191202558","volume":"8","author":"D. S. Franzblau","year":"1995","unstructured":"D. S. Franzblau. Combinatorial Algorithm for a Lower Bound on Frame Rigidity. SI AM Journal on Discrete Mathematics, 8(3):388\u2013400, 1995.","journal-title":"SI AM Journal on Discrete Mathematics"},{"issue":"5","key":"11_CR13","doi-asserted-by":"publisher","first-page":"245","DOI":"10.1016\/S0020-0190(99)00067-8","volume":"70","author":"D. S. Franzblau","year":"1999","unstructured":"D. S. Franzblau. Ear Decomposition with Bounds on Ear Length. Information Processing Letters, 70(5):245\u2013249, 1999.","journal-title":"Information Processing Letters"},{"issue":"1\u20133","key":"11_CR14","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0166-218X(99)00188-2","volume":"101","author":"D. S. Franzblau","year":"2000","unstructured":"D. S. Franzblau. Generic Rigidity of Molecular Graphs Via Ear Decomposition. Discrete Applied Mathematics, 101(1\u20133):131\u2013155, 2000.","journal-title":"Discrete Applied Mathematics"},{"key":"11_CR15","doi-asserted-by":"crossref","unstructured":"P. B. Gibbons, Y. Matias, and V. Ramachandran. Can shared-memory model serve as a bridging model for parallel computation? In Proceedings of the 9th annual ACM symposium on parallel algorithms and architectures, pages 72\u201383, Newport, RI, June 1997.","DOI":"10.1145\/258492.258500"},{"issue":"2","key":"11_CR16","doi-asserted-by":"publisher","first-page":"733","DOI":"10.1137\/S009753979427491","volume":"28","author":"P. B. Gibbons","year":"1998","unstructured":"P. B. Gibbons, Y. Matias, and V. Ramachandran. The Queue-Read Queue-Write PRAM Model: Accounting for Contention in Parallel Algorithms. SIAM Journal on Computing, 28(2):733\u2013769, 1998.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR17","unstructured":"B. Grayson, M. Dahlin, and V. Ramachandran. Experimental evaluation of QSM, a simple shared-memory model. In Proceedings of the 13th International Parallel Processing Symposium and 10th Symposium on Parallel and Distributed Processing (IPPS\/SPDP), pages 1\u20137, San Juan, Puerto Rico, April 1999."},{"key":"11_CR18","doi-asserted-by":"crossref","unstructured":"D. R. Helman and J. J\u00e1J\u00e1. Designing Practical Efficient Algorithms for Symmetric Multiprocessors. In Algorithm Engineering and Experimentation (ALENEX\u201999), pages 37\u201356, Baltimore, MD, January 1999.","DOI":"10.1007\/3-540-48518-X_3"},{"issue":"2","key":"11_CR19","doi-asserted-by":"publisher","first-page":"297","DOI":"10.1016\/0304-3975(96)00034-5","volume":"162","author":"T.-S. Hsu","year":"1996","unstructured":"T.-S. Hsu and V. Ramachandran. Efficient massively parallel implementation of some combinatorial algorithms. Theoretical Computer Science, 162(2):297\u2013322, 1996.","journal-title":"Theoretical Computer Science"},{"key":"11_CR20","unstructured":"T.-S. Hsu, V. Ramachandran, and N. Dean. Implementation of parallel graph algorithms on a massively parallel SIMD computer with virtual processing. In Proceedings of the 9th International Parallel Processing Symposium, pages 106\u2013112, Santa Barbara, CA, April 1995."},{"issue":"8","key":"11_CR21","doi-asserted-by":"publisher","first-page":"873","DOI":"10.1016\/0167-8191(93)90071-R","volume":"19","author":"L. Ibarra","year":"1993","unstructured":"L. Ibarra and D. Richards. Efficient Parallel Graph Algorithms Based on Open Ear Decomposition. Parallel Computing, 19(8):873\u2013886, 1993.","journal-title":"Parallel Computing"},{"key":"11_CR22","volume-title":"An Introduction to Parallel Algorithms","author":"J. J\u00e1J\u00e1","year":"1992","unstructured":"J. J\u00e1J\u00e1. An Introduction to Parallel Algorithms. Addison-Wesley Publishing Company, New York, 1992."},{"issue":"3","key":"11_CR23","doi-asserted-by":"publisher","first-page":"288","DOI":"10.1016\/0022-0000(91)90004-O","volume":"42","author":"A. Kanevsky","year":"1991","unstructured":"A. Kanevsky and V. Ramachandran. Improved Algorithms for Graph Four-Connectivity. Journal of Computer and System Sciences, 42(3):288\u2013306, 1991.","journal-title":"Journal of Computer and System Sciences"},{"issue":"1","key":"11_CR24","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1016\/S0304-3975(96)00065-5","volume":"168","author":"D. J. Kavvadias","year":"1996","unstructured":"D. J. Kavvadias, G. E. Pantziou, P. G. Spirakis, and C. D. Zaroliagis. Hammock-On-Ears Decomposition: A Technique for the Efficient Parallel Solution of Shortest Paths and Other Problems. Theoretical Computer Science, 168(1):121\u2013154, 1996.","journal-title":"Theoretical Computer Science"},{"issue":"1","key":"11_CR25","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1109\/71.841748","volume":"11","author":"A. Kazmierczak","year":"2000","unstructured":"A. Kazmierczak and S. Radhakrishnan. An Optimal Distributed Ear Decomposition Algorithm with Applications to Biconnectivity and Outerplanarity Testing. IEEE Transactions on Parallel and Distributed Systems, 11(1):110\u2013118, 2000.","journal-title":"IEEE Transactions on Parallel and Distributed Systems"},{"key":"11_CR26","unstructured":"J. Keller, C. W. Ke\u00dfler, and J. L. Tr\u00e4ff. Practical PRAM Programming. John Wiley & Sons, 2001."},{"key":"11_CR27","unstructured":"R. Ladner, J. D. Fix, and A. LaMarca. The cache performance of traversals and random accesses. In Proc. 10th Ann. ACM\/SIAM Symposium on Discrete Algorithms (SODA-99), pages 613\u2013622, Baltimore, MD, 1999."},{"key":"11_CR28","doi-asserted-by":"crossref","unstructured":"A. LaMarca and R. E. Ladner. The Influence of Caches on the Performance of Heaps. ACM Journal of Experimental Algorithmics, 1(4), 1996. http:\/\/www.jea.acm.org\/1996\/LaMarcaInfluence\/ .","DOI":"10.1145\/235141.235145"},{"key":"11_CR29","unstructured":"A. LaMarca and R. E. Ladner. The Influence of Caches on the Performance of Heaps. In Proceedings of the Eighth ACM\/SIAM Symposium on Discrete Algorithms, pages 370\u2013379, New Orleans, LA, 1997."},{"key":"11_CR30","doi-asserted-by":"crossref","unstructured":"L. Lov\u00e1sz. Computing Ears and Branchings in Parallel. In Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science (FOCS 85), pages 464\u2013467, Portland, Oregon, October 1985.","DOI":"10.1109\/SFCS.1985.16"},{"key":"11_CR31","unstructured":"Message Passing Interface Forum. MPI: A Message-Passing Interface Standard. Technical report, University of Tennessee, Knoxville, TN, June 1995. Version 1.1."},{"key":"11_CR32","unstructured":"G. L. Miller and V. Ramachandran. Efficient parallel ear decomposition with applications. Manuscript, UC Berkeley, MSRI, January 1986."},{"issue":"3","key":"11_CR33","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1016\/0304-3975(86)90153-2","volume":"47","author":"Y. Moan","year":"1986","unstructured":"Y. Moan, B. Schieber, and U. Vishkin. Parallel ear decomposition search (EDS) and st-numbering in graphs. Theoretical Computer Science, 47(3):277\u2013296, 1986.","journal-title":"Theoretical Computer Science"},{"key":"11_CR34","doi-asserted-by":"crossref","unstructured":"B. M. E. Moret. Towards a discipline of experimental algorithmics. In DIM ACS Monographs in Discrete Mathematics and Theoretical Computer Science. American Mathematical Society, 2001. To appear. Available at www.cs.unm.edu\/~moret\/dimacs.ps .","DOI":"10.1090\/dimacs\/059\/10"},{"key":"11_CR35","unstructured":"OpenMP Architecture Review Board. OpenMP: A Proposed Industry Standard API for Shared Memory Programming. http:\/\/www.openmp.org\/ , October 1997."},{"key":"11_CR36","unstructured":"Portable Applications Standards Committee of the IEEE. Information technology-Portable Operating System Interface (POSIX)-Part 1: System Application Program Interface (API), 1996-07-12 edition, 1996. ISO\/IEC 9945-1, ANSI\/IEEE Std. 1003.1."},{"key":"11_CR37","first-page":"275","volume-title":"Synthesis of Parallel Algorithms","author":"V. Ramachandran","year":"1993","unstructured":"V. Ramachandran. Parallel Open Ear Decomposition with Applications to Graph Biconnectivity and Triconnectivity. In J. H. Reif, editor, Synthesis of Parallel Algorithms, pages 275\u2013340. Morgan Kaufman, San Mateo, CA, 1993."},{"key":"11_CR38","first-page":"1","volume-title":"Algorithms for Parallel Processing","author":"V. Ramachandran","year":"1999","unstructured":"V. Ramachandran. A General-Purpose Shared-Memory Model for Parallel Computation. In M. T. Heath, A. Ranade, and R. S. Schreiber, editors, Algorithms for Parallel Processing, volume 105, pages 1\u201318. Springer-Verlag, New York, 1999."},{"key":"11_CR39","doi-asserted-by":"crossref","unstructured":"M. Reid-Miller. List ranking and list scan on the Cray C-90. In Proceedings Symposium on Parallel Algorithms and Architectures, pages 104\u2013113, Cape May, NJ, June 1994.","DOI":"10.1145\/181014.181049"},{"issue":"3","key":"11_CR40","doi-asserted-by":"crossref","first-page":"344","DOI":"10.1006\/jcss.1996.0074","volume":"53","author":"M. Reid-Miller","year":"1996","unstructured":"M. Reid-Miller. List ranking and list scan on the Cray C-90. Journal of Computer and System Sciences, 53(3):344\u2013356, December 1996.","journal-title":"Journal of Computer and System Sciences"},{"key":"11_CR41","unstructured":"J. H. Reif, editor. Synthesis of Parallel Algorithms. Morgan Kaufmann Publishers, 1993."},{"issue":"4","key":"11_CR42","doi-asserted-by":"publisher","first-page":"682","DOI":"10.1137\/0210051","volume":"10","author":"C. Savage","year":"1981","unstructured":"C. Savage and J. J\u00e1J\u00e1. Fast, Efficient Parallel Algorithms for Some Graph Problems. SIAM Journal on Computing, 10(4):682\u2013691, 1981.","journal-title":"SIAM Journal on Computing"},{"key":"11_CR43","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/BFb0014497","volume-title":"Applied Computational Geometry: Towards Geometric Engineering","author":"J. R. Shewchuk","year":"1996","unstructured":"J. R. Shewchuk. Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In M. C. Lin and D. Manocha, editors, Applied Computational Geometry: Towards Geometric Engineering, volume 1148 of Lecture Notes in Computer Science, pages 203\u2013222. Springer-Verlag, May 1996. From the First ACM Workshop on Applied Computational Geometry."},{"key":"11_CR44","doi-asserted-by":"crossref","unstructured":"J. Sibeyn. Better trade-offs for parallel list ranking. In Proceedings of the 9th annual ACM symposium on parallel algorithms and architectures, pages 221\u2013230, Newport, RI, June 1997.","DOI":"10.1145\/258492.258514"},{"key":"11_CR45","doi-asserted-by":"publisher","first-page":"110","DOI":"10.1007\/BF01185207","volume":"12","author":"J. Vitter","year":"1994","unstructured":"J. Vitter and E. Shriver. Algorithms for Parallel Memory I: Two-Level Memories. Algorithmica, 12:110\u2013147, 1994.","journal-title":"Algorithmica"},{"key":"11_CR46","doi-asserted-by":"publisher","first-page":"339","DOI":"10.2307\/1989545","volume":"34","author":"H. Whitney","year":"1932","unstructured":"H. Whitney. Non-Separable and Planar Graphs. Transactions of the American Mathematical Society, 34:339\u2013362, 1932.","journal-title":"Transactions of the American Mathematical Society"}],"container-title":["Lecture Notes in Computer Science","Algorithm Engineering"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-44688-5_11","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,1,20]],"date-time":"2025-01-20T18:06:50Z","timestamp":1737396410000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/3-540-44688-5_11"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2001]]},"ISBN":["9783540425007","9783540446880"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/3-540-44688-5_11","relation":{},"ISSN":["0302-9743"],"issn-type":[{"type":"print","value":"0302-9743"}],"subject":[],"published":{"date-parts":[[2001]]},"assertion":[{"value":"17 August 2001","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}