C. J. Alpert and A. B. Kahng, Recent directions in netlist partitioning: a survey, VLSI Journal, vol.19, issue.1-2, pp.1-81, 1995.

C. J. Alpert, A. E. Caldwell, A. B. Kahng, and I. L. Markov, Hypergraph partitioning with fixed vertices, IEEE Transactions on Computer-Aided Design, vol.19, issue.2, pp.267-272, 2000.

C. Ashcraft, Compressed graphs and the minimum degree algorithm, SIAM Journal on Scientific Computing, vol.16, issue.6, pp.1404-1411, 1995.

C. Aykanat, A. Pinar, and Ü. V. , Permuting sparse rectangular matrices into block-diagonal form, SIAM Journal of Scientific Computing, vol.25, issue.6, pp.1860-1879, 2004.

C. Berge, Graphs and Hypergraphs, 1973.

R. H. Bisseling, J. Byrka, S. Cerav-erbas, N. Gvozdenovic, M. Lorenz et al., Partitioning a call graph, Second International Workshop on Combinatorial Scientific Computing, 2005.

R. H. Bisseling and I. Flesch, Mondriaan sparse matrix partitioning for attacking cryptosystems by a parallel block Lanczos algorithm: a case study, Parallel Computing, vol.32, issue.7, pp.551-567, 2006.

T. N. Bui and C. Jones, A heuristic for reducing fill in sparse matrix factorization, Proceedings of the Sixth SIAM Conference on Parallel Processing for Scientific Computing, pp.445-452, 1993.

A. Caldwell, A. Kahng, and I. Markov, Improved algorithms for hypergraph bipartitioning, Proceedings of the IEEE ACM Asia and South Pacific Design Automation Conference, pp.661-666, 2000.

B. B. Cambazoglu and C. Aykanat, Hypergraph-partitioning-based remapping models for image-space-parallel direct volume rendering of unstructured grids, IEEE Transactions on Parallel and Distributed Systems, vol.18, issue.1, pp.3-16, 2007.

C. Chang, T. M. Kurc, A. Sussman, Ü. V. Atalyürek, and J. H. Saltz, A hypergraphbased workload partitioning strategy for parallel data aggregation, SIAM Conference on Parallel Processing for Scientific Computing, 2001.

G. Chartrand and O. R. Oellermann, Applied and Algorithmic Graph Theory, 1993.

C. Clifton, R. Cooley, and J. Rennie, TopCat: Data mining for topic identification in a text corpus, IEEE Transactions on Knowledge and Data Engineering, vol.16, issue.8, pp.949-964, 2004.

Ü. V. , , vol.98

Ü. V. Atalyürek and C. Aykanat, Decomposing irregularly sparse matrices for parallel matrix-vector multiplication, Lecture Notes in Computer Science, vol.1117, pp.75-86, 1996.

Ü. V. Atalyürek and C. Aykanat, PaToH: partitioning tool for hypergraphs, 1999.

Ü. V. Atalyürek and C. Aykanat, Hypergraph-partitioning-based decomposition for parallel sparse-matrix vector multiplication, IEEE Transactions on Parallel and Distributed Systems, vol.10, issue.7, pp.673-693, 1999.

Ü. V. Atalyürek and C. Aykanat, A fine-grain hypergraph model for 2D decomposition of sparse matrices, Proceedings of the 15th International Parallel & Distributed Processing Symposium, p.118, 2001.

Ü. V. Atalyürek and C. Aykanat, A hypergraph-partitioning approach for coarsegrain decomposition, Proceedings of the 2001 ACM/IEEE Conference on Supercomputing, p.28, 2001.

A. Dasdan and C. Aykanat, Two novel multiway circuit partitioning algorithms using relaxed locking, IEEE Transactions Computer-Aided Design of Integrated Circuits and Systems, vol.16, issue.2, pp.169-178, 1997.

T. Davis, NA Digest, vol.97, issue.23, 1997.

E. Demir, C. Aykanat, and B. B. Cambazoglu, Clustering spatial networks for aggregate query processing: a hypergraph approach, Information Systems

E. Demir, C. Aykanat, and B. B. Cambazoglu, A link-based storage scheme for efficient aggregate query processing on clustered road networks, Under review at IEEE Transactions on Knowledge and Data Engineering

K. D. Devine, E. G. Boman, R. T. Heaphy, B. Hendrickson, and C. Vaughan, Zoltan data management services for parallel dynamic applications, Computing in Science and Engineering, vol.4, issue.2, pp.90-97, 2002.

K. D. Devine, E. G. Boman, R. T. Heaphy, R. Bisseling, and Ü. V. , Parallel hypergraph partitioning for scientific computing, Proceedings of the IEEE International Parallel & Distributed Processing Symposium, 2006.

N. J. Dingle, P. G. Harrison, and W. J. Knottenbelt, Uniformization and hypergraph partitioning for the distributed computation of response time densities in very large Markov models, Journal of Parallel and Distributed Computing, vol.64, issue.8, pp.908-920, 2004.

I. S. Duff, S. Riyavong, and M. B. Van-gijzen, Parallel preconditioners based on partitioning sparse matrices, CERFACS, 2004.

C. M. Fiduccia and R. M. Mattheyses, A linear-time heuristic for improving network partitions, Proceedings of the 19th ACM/IEEE Design Automation Conference, pp.175-181, 1982.

M. K. Goldberg and M. Burnstein, Heuristic improvement technique for bisection of VLSI networks, Proceedings of the IEEE International Conference on Computer Design, pp.122-125, 1983.

B. Hendrickson and R. Leland, The Chaco user's guide: Version 2.0, pp.94-2692, 1994.

B. Hendrickson and E. Rothberg, Improving the run time and quality of nested dissection ordering, SIAM Journal on Scientific Computing, vol.20, issue.2, pp.468-489, 1998.

G. Karypis, R. Aggarwal, V. Kumar, and S. Shekhar, Multilevel hypergraph partitioning: applications in VLSI domain, IEEE Transactions on Very Large Scale Integration Systems, vol.7, issue.1, pp.69-79, 1999.

G. Karypis and V. Kumar, hMETIS: a hypergraph partitioning package, 1998.

G. Karypis and V. Kumar, MeTiS: A software package for partitioning unstructured graphs, partitioning meshes and computing fill-reducing orderings of sparse matrices, 1998.

G. Karypis and V. Kumar, Multilevel algorithms for multi-constraint graph partitioning, Proceedings of the 1998 ACM/IEEE Conference on Supercomputing, pp.1-13, 1998.

G. Karypis and V. Kumar, Multilevel k-way hypergraph partitioning, VLSI Design, vol.11, issue.3, pp.285-300, 2000.

K. Kaya and C. Aykanat, Iterative-improvement-based heuristics for adaptive scheduling of tasks sharing files on heterogeneous master-slave environments, IEEE Transactions on Parallel and Distributed Systems, vol.17, issue.8, pp.883-896, 2006.

K. Kaya, B. Ucar, and C. Aykanat, Heuristics for scheduling file-sharing tasks on heterogeneous systems with distributed repositories, Journal of Parallel and Distributed Computing, vol.67, issue.3, pp.271-285, 2007.
URL : https://hal.archives-ouvertes.fr/hal-00803511

B. W. Kernighan and S. Lin, An efficient heuristic procedure for partitioning graphs, Bell System Technical Journal, vol.49, pp.291-307, 1970.

G. Khanna, N. Vydyanathan, T. M. Kurc, Ü. V. , P. Wyckoff et al., A hypergraph partitioning based approach for scheduling of tasks with batch-shared IO, Proceedings of Cluster Computing and Grid, 2005.

M. Koyuturk and C. Aykanat, Iterative-improvement-based declustering heuristics for multi-disk databases, Information Systems, vol.30, issue.1, pp.47-70, 2005.

T. Lengauer, Combinatorial Algorithms for Integrated Circuit Layout, 1990.

D. R. Liu and M. Y. Wu, A hypergraph based approach to declustering problems, Distributed and Parallel Databases, vol.10, pp.269-288, 2001.

M. M. Ozdal and C. Aykanat, Hypergraph models and algorithms for data-patternbased clustering, Data Mining and Knowledge Discovery, vol.9, issue.1, pp.29-57, 2004.

D. G. Schweikert and B. W. Kernighan, A proper model for the partitioning of electrical circuits, Proceedings of the 9th Workshop on Design Automation, pp.57-62, 1972.

S. Shekhar, C. Lu, S. Chawla, and S. Ravada, Efficient join-index-based spatialjoin processing: a clustering approach, IEEE Transactions on Knowledge and Data Engineering, vol.14, issue.6, pp.1400-1421, 2002.

H. D. Simon and S. Teng, How good is recursive bisection?, SIAM Journal on Scientific Computing, vol.18, issue.5, pp.1436-1445, 1997.

A. Trifunovic and W. J. Knottenbelt, Parkway 2.0: a parallel multilevel hypergraph partitioning tool, Proceedings of the International Symposium on Computer and Information Sciences, pp.789-800, 2004.

B. Uçar and C. Aykanat, Encapsulating multiple communication-cost metrics in partitioning sparse rectangular matrices for parallel matrix-vector multiplies, SIAM Journal on Scientific Computing, vol.25, issue.6, pp.1837-1859, 2004.

B. Uçar and C. Aykanat, Revisiting hypergraph models for sparse matrix partitioning, SIAM Review

B. Uçar and C. Aykanat, Partitioning sparse matrices for parallel preconditioned iterative methods, SIAM Journal on Scientific Computing, vol.29, issue.4, pp.1683-1709, 2007.

B. Uçar, C. Aykanat, M. C. P?nar, and T. Malas, Parallel image restoration using surrogate constraints methods, Journal of Parallel and Distributed Computing, vol.67, issue.2, pp.186-204, 2007.

B. Vastenhouw and R. H. Bisseling, A two-dimensional data distribution method for parallel sparse matrix-vector multiplication, SIAM Review, vol.47, issue.1, pp.67-95, 2005.

C. Walshaw, M. Cross, and K. Mcmanus, Multiphase mesh partitioning, Applied Mathematical Modelling, vol.25, pp.123-140, 2000.