{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T16:39:39Z","timestamp":1772296779266,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":44,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783540405542","type":"print"},{"value":"9783540450849","type":"electronic"}],"license":[{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2003,1,1]],"date-time":"2003-01-01T00:00:00Z","timestamp":1041379200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2003]]},"DOI":"10.1007\/3-540-45084-x_8","type":"book-chapter","created":{"date-parts":[[2007,7,3]],"date-time":"2007-07-03T16:05:12Z","timestamp":1183478712000},"page":"183-209","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":11,"title":["Congestion and Almost Invariant Sets in Dynamical Systems"],"prefix":"10.1007","author":[{"given":"Michael","family":"Dellnitz","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Robert","family":"Preis","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2003,6,24]]},"reference":[{"key":"8_CR1","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1017\/S096354839700299X","volume":"6","author":"N. Alon","year":"1997","unstructured":"N. Alon. On the edge-expansion of graphs. Combinatories, Probability and Computing, 6:145\u2013152, 1997.","journal-title":"Combinatories, Probability and Computing"},{"key":"8_CR2","series-title":"Lect Notes Comput Sci","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1007\/3-540-40064-8_4","volume-title":"Workshop on Graph-Theoretic Concepts in Computer Science (WG)","author":"S.L. Bezroukov","year":"2000","unstructured":"S.L. Bezroukov, R. Els\u00e4sser, B. Monien, R. Preis, and J.-P. Tillich. New spectral lower bounds on the bisection width of graphs. In Workshop on Graph-Theoretic Concepts in Computer Science (WG), LNCS 1928, pages 23\u201334, 2000."},{"key":"8_CR3","unstructured":"N. Bouhmala. Impact of different graph coarsening schemes on the quality of the partitions. Technical Report RT98\/05-01, University of Neuchatel, Department of Computer Science, 1998."},{"key":"8_CR4","doi-asserted-by":"crossref","unstructured":"F.R.K. Chung. Spectral Graph Theory, volume 92 of CBMS Regional conference series in mathematics. American Mathematical Society, 1997.","DOI":"10.1090\/cbms\/092"},{"key":"8_CR5","unstructured":"T.H. Cormen, C.E. Leiserson, and R.L. Rivest. Introduction to Algorithms. MIT Press, 1990."},{"key":"8_CR6","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1007\/s002110050240","volume":"75","author":"M. Dellnitz","year":"1997","unstructured":"M. Dellnitz and A. Hohmann. A subdivision algorithm for the computation of unstable manifolds and global attractors. Numerische Mathematik, 75:293\u2013317, 1997.","journal-title":"Numerische Mathematik"},{"issue":"2","key":"8_CR7","doi-asserted-by":"publisher","first-page":"491","DOI":"10.1137\/S0036142996313002","volume":"36","author":"M. Dellnitz","year":"1999","unstructured":"M. Dellnitz and O. Junge. On the approximation of complicated dynamical behavior. SIAM J. Numer. Anal., 36(2):491\u2013515, 1999.","journal-title":"SIAM J. Numer. Anal."},{"key":"8_CR8","series-title":"Lect Notes Comput Sci","volume-title":"Computational Molecular Dynamics: Challenges, Methods, Ideas","author":"P. Deuflhard","year":"1998","unstructured":"P. Deuflhard, M. Dellnitz, O. Junge, and Ch. Sch\u00fctte. Computation of essential molecular dynamics by subdivision techniques. In Deuflhard et al., editor, Computational Molecular Dynamics: Challenges, Methods, Ideas, LNCSE 4, 1998."},{"key":"8_CR9","doi-asserted-by":"publisher","first-page":"39","DOI":"10.1016\/S0024-3795(00)00095-1","volume":"315","author":"P. Deuflhard","year":"2000","unstructured":"P. Deuflhard, W. Huisinga, A. Fischer, and Ch. Sch\u00fctte. Identification of almost invariant aggregates in reversible nearly uncoupled markov chains. Lin. Alg. Appl., 315:39\u201359, 2000.","journal-title":"Lin. Alg. Appl."},{"issue":"7","key":"8_CR10","doi-asserted-by":"publisher","first-page":"789","DOI":"10.1016\/S0167-8191(99)00018-6","volume":"25","author":"R. Diekmann","year":"1999","unstructured":"R. Diekmann, A. Frommer, and B. Monien. Efficient schemes for nearest neighbor load balancing. Parallel Computing, 25(7):789\u2013812, 1999.","journal-title":"Parallel Computing"},{"key":"8_CR11","doi-asserted-by":"crossref","unstructured":"R. Diekmann, B. Monien, and R. Preis. Using helpful sets to improve graph bisections. In D.F. Hsu, A.L. Rosenberg, and D. Sotteau, editors, Interconnection Networks and Mapping and Scheduling Parallel Computations, volume 21 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, pages 57\u201373. AMS, 1995.","DOI":"10.1090\/dimacs\/021\/06"},{"key":"8_CR12","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"280","DOI":"10.1007\/3-540-48311-X_36","volume-title":"Euro Par\u201999 Parallel Processing","author":"R. Els\u00e4sser","year":"1999","unstructured":"R. Els\u00e4sser, A. Frommer, B. Monien, and R. Preis. Optimal and alternating-direction loadbalancing schemes. In P. Amestoy et al., editor, Euro Par\u201999 Parallel Processing, LNCS 1685, pages 280\u2013290, 1999."},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"R. Els\u00e4sser, T. L\u00fccking, and B. Monien. New spectral bounds on k-partitioning of graphs. In Proc. of the Symposium on Parallel Algorithms and Architectures (SPAA), pages 255\u2013270, 2001.","DOI":"10.1145\/378580.378677"},{"key":"8_CR14","doi-asserted-by":"crossref","unstructured":"R. Els\u00e4sser, B. Monien, and R. Preis. Diffusive load balancing schemes on heterogeneous networks. In 12th ACM Symp. on Parallel Algorithms and Architectures (SPAA), pages 30\u201338, 2000.","DOI":"10.1145\/341800.341805"},{"key":"8_CR15","doi-asserted-by":"crossref","unstructured":"C.M. Fiduccia and R.M. Mattheyses. A linear-time heuristic for improving network partitions. In Proc. IEEE Design Automation Conf., pages 175\u2013181, 1982.","DOI":"10.1109\/DAC.1982.1585498"},{"issue":"100","key":"8_CR16","doi-asserted-by":"crossref","first-page":"619","DOI":"10.21136\/CMJ.1975.101357","volume":"25","author":"M. Fiedler","year":"1975","unstructured":"M. Fiedler. A property of eigenvectors of nonnegative symmetric matrices and its application to graph theory. Czechoslovak Mathematical J., Praha, 25(100):619\u2013633, 1975.","journal-title":"Czechoslovak Mathematical J., Praha"},{"key":"8_CR17","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","DOI":"10.1007\/3-540-36383-1","volume-title":"Proc. of the 3rd International Workshop on Algorithms for Macromolecular Modeling","author":"A. Fischer","year":"2002","unstructured":"A. Fischer, Ch. Sch\u00fctte, P. Deuflhard, and F. Cordes. Hierarchical uncoupling-coupling of metastable conformations. In Schlick and Gan, editors, Proc. of the 3rd International Workshop on Algorithms for Macromolecular Modeling, LNCSE 24, 2002."},{"key":"8_CR18","unstructured":"G. Froyland and M. Dellnitz. Detecting and locating near-optimal almost-invariant sets and cycles. Technical report, DFG-Priority Program 1095: \u201cAnalysis, Modeling and Simulation of Multiscale Problems\u201d, 2001."},{"key":"8_CR19","unstructured":"G. Froyland and M. Dellnitz. \u03bc almost-invariant sets and adaptive boundary refinement. manuscript, 2003."},{"key":"8_CR20","unstructured":"M.R. Garey and D.S. Johnson. Computers and Intractability \u2014 A Guide to the Theory of NP-Completeness. Freemann, 1979."},{"key":"8_CR21","doi-asserted-by":"publisher","first-page":"171","DOI":"10.1147\/rd.411.0171","volume":"41","author":"A. Gupta","year":"1997","unstructured":"A. Gupta. Fast and effective algorithms for graph partitioning and sparse matrix recordering. IBM J. of Research and Development, 41:171\u2013183, 1997.","journal-title":"IBM J. of Research and Development"},{"key":"8_CR22","series-title":"Technical Report","volume-title":"The chaco user\u2019s guide: Version 2.0.","author":"B. Hendrickson","year":"1994","unstructured":"B. Hendrickson and R. Leland. The chaco user\u2019s guide: Version 2.0. Technical Report SAND94-2692, Sandia National Laboratories, Albuquerque, NM, 1994."},{"key":"8_CR23","doi-asserted-by":"crossref","unstructured":"B. Hendrickson and R. Leland. A multilevel algorithm for partitioning graphs. In Proc. Supercomputing\u2019 95. ACM, 1995.","DOI":"10.1145\/224170.224228"},{"key":"8_CR24","doi-asserted-by":"crossref","unstructured":"J. Hromkovi\u010d and B. Monien. The bisection problem for graphs of degree 4 (configuring transputer systems). In Buchmann, Ganzinger, and Paul, editors, Festschriftzum 60. Geburtstag von G\u00fcnter Hotz, pages 215\u2013234. Teubner, 1992.","DOI":"10.1007\/978-3-322-95233-2_13"},{"key":"8_CR25","unstructured":"W. Huisinga. Metastability of Markovian systems. Phd thesis, Freie Universit\u00e4t Berlin, 2001."},{"key":"8_CR26","unstructured":"G. Karypis and V. Kumar. METIS Manual, Version 4.0. University of Minnesota, Department of Computer Science, 1998."},{"key":"8_CR27","doi-asserted-by":"publisher","first-page":"96","DOI":"10.1006\/jpdc.1997.1404","volume":"48","author":"G. Karypis","year":"1998","unstructured":"G. Karypis and V. Kumar. Multilevel k-way partitioning scheme for irregular graphs. J. of Parallel and Distributed Computing, 48:96\u2013129, 1998.","journal-title":"J. of Parallel and Distributed Computing"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"G. Karypis and V. Kumar. A fast and high quality multilevel scheme for partitioning irregular graphs. SIAM J. on Scientific Computing, 20(1), 1999.","DOI":"10.1137\/S1064827595287997"},{"key":"8_CR29","doi-asserted-by":"crossref","unstructured":"B.W. Kernighan and S. Lin. An effective heuristic procedure for partitioning graphs. The Bell Systems Technical J., pages 291\u2013307, 1970.","DOI":"10.1002\/j.1538-7305.1970.tb01770.x"},{"key":"8_CR30","doi-asserted-by":"crossref","unstructured":"F.T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, 1992.","DOI":"10.1016\/B978-1-4832-0772-8.50005-4"},{"key":"8_CR31","doi-asserted-by":"crossref","unstructured":"B. Mohar. Some applications of laplace eigenvalues of graphs. In Graph Symmetry: Algebraic Methods and Applications, NATO ASI Ser. C 497, pages 225\u2013275, 1997.","DOI":"10.1007\/978-94-015-8937-6_6"},{"key":"8_CR32","unstructured":"B. Monien and R. Diekmann. A local graph partitioning heuristic meeting bisection bounds. In 8th SIAM Conf. on Parallel Processing for Scientific Computing, 1997."},{"key":"8_CR33","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"524","DOI":"10.1007\/3-540-44683-4_46","volume-title":"26th International Symposium on Mathematical Foundations of Computer Science (MFCS)","author":"B. Monien","year":"2001","unstructured":"B. Monien and R. Preis. Bisection width of 3-and 4-regular graphs. In 26th International Symposium on Mathematical Foundations of Computer Science (MFCS), LNCS 2136, pages 524\u2013536, 2001."},{"issue":"12","key":"8_CR34","doi-asserted-by":"publisher","first-page":"1609","DOI":"10.1016\/S0167-8191(00)00049-1","volume":"26","author":"B. Monien","year":"2000","unstructured":"B. Monien, R. Preis, and R. Diekmann. Quality matching and local improvement for multilevel graph-partitioning. Parallel Computing, 26(12):1609\u20131634, 2000.","journal-title":"Parallel Computing"},{"key":"8_CR35","unstructured":"F. Pellegrini. SCOTCH 3.1 user\u2019s guide. Technical Report 1137-96, LaBRI, University of Bordeaux, 1996."},{"key":"8_CR36","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1155\/1994\/715918","volume":"3","author":"R. Ponnusamy","year":"1994","unstructured":"R. Ponnusamy, N. Mansour, A. Choudhary, and G.C. Fox. Graph contraction for mapping data on parallel computers: A quality-cost tradeoff. Scientific Programming, 3:73\u201382, 1994.","journal-title":"Scientific Programming"},{"issue":"3","key":"8_CR37","doi-asserted-by":"publisher","first-page":"430","DOI":"10.1137\/0611030","volume":"11","author":"A. Pothen","year":"1990","unstructured":"A. Pothen, H.D. Simon, and K.P. Liu. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. on Matrix Analysis and Applications, 11(3):430\u2013452, 1990.","journal-title":"SIAM J. on Matrix Analysis and Applications"},{"key":"8_CR38","volume-title":"The PARTY Graphpartitioning-Library, User Manual \u2014 Version 1.99","author":"R. Preis","year":"1998","unstructured":"R. Preis. The PARTY Graphpartitioning-Library, User Manual \u2014 Version 1.99. Universit\u00e4t Paderborn, Germany, 1998."},{"key":"8_CR39","volume-title":"Heinz Nixdorf Institut Verlagsschriftenreihe","author":"R. Preis","year":"2000","unstructured":"R. Preis. Analyses and Design of Efficient Graph Partitioning Methods. Heinz Nixdorf Institut Verlagsschriftenreihe, 2000. Dissertation, Universit\u00e4t Paderborn, Germany."},{"key":"8_CR40","unstructured":"Ch. Sch\u00fctte. Conformational Dynamics: Modelling, Theory, Algorithm, and Application to Biomolecules. Habilitation thesis, Freie Universit\u00e4t Berlin, 1999."},{"key":"8_CR41","series-title":"Lect Notes Comput Sci","doi-asserted-by":"crossref","first-page":"391","DOI":"10.1007\/3-540-44676-1_33","volume-title":"Proc. European Symposium on Algorithms (ESA)","author":"N. Sensen","year":"2001","unstructured":"N. Sensen. Lower bounds and exact algorithms for the graph partitioning problem using multicommodity flows. In Proc. European Symposium on Algorithms (ESA), LNCS 2161, pages 391\u2013403, 2001."},{"issue":"5","key":"8_CR42","doi-asserted-by":"publisher","first-page":"1436","DOI":"10.1137\/S1064827593255135","volume":"18","author":"H.D. Simon","year":"1997","unstructured":"H.D. Simon and S.-H. Teng. How good is recursive bisection? SIAM J. on Scientific Computing, 18(5): 1436\u20131445, 1997.","journal-title":"SIAM J. on Scientific Computing"},{"key":"8_CR43","doi-asserted-by":"crossref","unstructured":"A. Sinclair. Algorithms for Random Generation & Counting: A Markov Chain Approach. Progress in Theoretical Computer Science. Birkh\u00e4user, 1993.","DOI":"10.1007\/978-1-4612-0323-0"},{"key":"8_CR44","unstructured":"C. Walshaw. The Jostle user manual: Version 2.2. University of Greenwich, 2000."}],"container-title":["Lecture Notes in Computer Science","Symbolic and Numerical Scientific Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/3-540-45084-X_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,2,17]],"date-time":"2023-02-17T14:19:40Z","timestamp":1676643580000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/3-540-45084-X_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2003]]},"ISBN":["9783540405542","9783540450849"],"references-count":44,"URL":"https:\/\/doi.org\/10.1007\/3-540-45084-x_8","relation":{},"ISSN":["0302-9743"],"issn-type":[{"value":"0302-9743","type":"print"}],"subject":[],"published":{"date-parts":[[2003]]},"assertion":[{"value":"24 June 2003","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}}]}}