Constrained Min-Cut Replication for K-Way Hypergraph Partitioning

References

• Alpert CJ, Kahng AB (1995) Recent directions in netlist partitioning: A survey. Integr. VLSI J. 19:1–81.Crossref, Google Scholar
• Boley D, Gini M, Gross R, (Sam) Han E-H, Hastings K, Karypis G, Kumar V, Mobasher B, Moore J (1999) Document categorization and query generation on the world wide web using WebACE. Artificial Intelligence Rev. 13:365–391.Crossref, Google Scholar
• Brinkhoff T (2002) A framework for generating network-based moving objects. Geoinformatica 6:153–180.Crossref, Google Scholar
• Bureau U.S. Census (2002) Topologically integrated geographic encoding and referencing system (TIGER). U.S. Census Bureau. Accessed September 2009, http://www.census.gov/geo/www/tiger/.Google Scholar
• Cambazoglu BB, Aykanat C (2006) A term-based inverted index organization for communication-efficient parallel query processing. Proc. IFIP Intenat. Conf. Network Parallel Comput. NPC, Tokyo, Japan.Google Scholar
• Catalyurek UV, Aykanat C (1999) PaToH: Partitioning tool for hypergraphs. Technical report BU-CE-9915, Department of Computer Engineering, Bilkent University, Ankara, Turkey.Google Scholar
• Cho J, Garcia-Molina H, Haveliwala T, Lam W, Paepcke A, Raghavan S, Wesley G (2004) Stanford WebBase components and applications. Technical report 2004-34, Stanford InfoLab, Stanford University, Stanford, CA.Google Scholar
• Davis TA, Hu Y (2011) The University of Florida sparse matrix collection. ACM Trans. Math. Software 38:1:1–1:25.Crossref, Google Scholar
• Demir E, Aykanat C, Cambazoglu BB (2008) Clustering spatial networks for aggregate query processing: A hypergraph approach. Inform. System 33:1–17.Crossref, Google Scholar
• Dulmage AL, Mendelsohn NS (1958) Coverings of bipartite graphs. Can. J. Math. 10:517–534.Crossref, Google Scholar
• Dulmage AL, Mendelsohn NS (1959) A structure theory of bipartite graphs of finite exterior dimension. Trans. Roy. Soc. Can. Sec. 3:1–13.Google Scholar
• Dulmage AL, Mendelsohn NS (1963) Two algorithms for bipartite graphs. J. Soc. Ind. Appl. Math. 2:183–194.Crossref, Google Scholar
• Enos M, Hauck S, Sarrafzadeh M (1997) Replication for logic bipartitioning. Computer-Aided Design, 1997. Digest of Technical Papers, 1997 IEEE/ACM International Conference. (IEEE Computer Society, Washington, DC), 342–349.Crossref, Google Scholar
• Garey MR, Johnson DS (1990) Computers and Intractability; A Guide to the Theory of NP-Completeness (W. H. Freeman & Co., New York).Google Scholar
• Goldschmidt O, Nehme D, Yu G (1994) Note: On the set-union knapsack problem. Naval Res. Logist. (NRL) 41:833–842.Crossref, Google Scholar
• Hotho A, Jäschke R, Schmitz C, Stumme G (2006) Information retrieval in folksonomies: Search and ranking. The Semantic Web: Research and Applications, Vol. 4011 (Springer-Verlag, Berlin), 411–426.Crossref, Google Scholar
• Hwang J, El Gamal A (1992) Optimal replication for min-cut partitioning. ICCAD '92: Proc. 1992 IEEE/ACM Internat. Conf. Comput.-Aided Design (IEEE Computer Society Press, Los Alamitos, CA), 432–435.Crossref, Google Scholar
• Hwang LJ (1994) Replication in partitioned networks. Ph.D. thesis, Stanford University.Google Scholar
• Johnson DM, Dulmage AL, Mendelsohn NS (1962) Connectivity and reducibility of graphs. Can. J. Math. 14:529–539.Crossref, Google Scholar
• Kring C, Newton AR (1991) A cell-replicating approach to mincut-based circuit partitioning. Comput.-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE Internat. Conf., Santa Clara, CA, 2–5.Crossref, Google Scholar
• Kužnar R, Brglez F, Zajc B (1994) Multi-way netlist partitioning into heterogeneous FPGAs and minimization of total device cost and interconnect. DAC '94: Proc. 31st Annual Design Automation Conf. (ACM, New York), 238–243.Crossref, Google Scholar
• Lengauer T (1990) Combinatorial Algorithms for Integrated Circuit Layout (Willey–Teubner, Chichester, UK).Crossref, Google Scholar
• Murgai R, Brayton RK, Sangiovanni-Vincentelli A (1991) On clustering for minimum delay/area. Comput.-Aided Design, 1991. ICCAD-91. Digest of Technical Papers., 1991 IEEE Internat. Conf., Santa Clara, CA, 6–9.Crossref, Google Scholar
• Pothen A (1984) Sparse null bases and marriage theorems. Ph.D. thesis, Cornell University, Ithaca, NY.Google Scholar
• Pothen A, Fan C-J (1990) Computing the block triangular form of a sparse matrix. ACM Trans. Math. Software 16:303–324.Crossref, Google Scholar
• Russo RL, Oden PH, Wolff PK (1971) A heuristic procedure for the partitioning and mapping of computer logic graphs. IEEE Trans. Comput. 20:1455–1462.Crossref, Google Scholar
• Selvitopi OR, Turk A, Aykanat C (2012) Replicated partitioning for undirected hypergraphs. J. Parallel Distrib. Comput. 72:547–563.Crossref, Google Scholar
• Shekhar S, Lu C-T, Chawla S, Ravada S (2002) Efficient join-index-based spatial-join processing: A clustering approach. IEEE Trans. Knowledge Data Engrg. 14:1400–1421.Crossref, Google Scholar
• Tarjan R (1972) Depth-first search and linear graph algorithms. SIAM J. Comput. 1:146–160.Crossref, Google Scholar
• U.S. Department of Transportation (2004) Federal Highway Administration, the national highway planning network. Accessed September 2009, http://www.fhwa.dot.gov/planning/nhpn/.Google Scholar
• Yang HH, Wong DF (1995) New algorithms for min-cut replication in partitioned circuits. ICCAD '95: Proc. 1995 IEEE/ACM Internat. Conf. Comput.-Aided Design (IEEE Computer Society, Washington, DC), 216–222.Crossref, Google Scholar