A class of bounded approximation algorithms for graph partitioning

This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These a...

Full description

Saved in:
Bibliographic Details
Published in:Networks 1990-03, Vol.20 (2), p.181-195
Main Authors: Feo, Thomas A., Khellaf, Mallek
Format: Article
Language:English
Subjects:
Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by cdi_FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323
cites cdi_FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323
container_end_page 195
container_issue 2
container_start_page 181
container_title Networks
container_volume 20
creator Feo, Thomas A.
Khellaf, Mallek
description This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.
doi_str_mv 10.1002/net.3230200205
format article
fullrecord <record><control><sourceid>istex_cross</sourceid><recordid>TN_cdi_crossref_primary_10_1002_net_3230200205</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><sourcerecordid>ark_67375_WNG_FPPXWGRK_4</sourcerecordid><originalsourceid>FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323</originalsourceid><addsrcrecordid>eNqFkM9PwjAUxxujiYhePfficfjarut2RIJoJEgMBm9NWTuojm1pZ4T_3pIZiSdPL-_H573v-yJ0TWBAAOhtZdoBowxoSICfoB6BTEQATJyiXqilEYOYn6ML798BCOEk7aG7Ic5L5T2uC7yqPyttNFZN4-qd3arW1hVW5bp2tt1sPS5qh9dONRvcKNfaQ9tW60t0VqjSm6uf2Eev9-PF6CGaPk8eR8NplMeU8YilFIqE5XGqMlOQmCVqFXRSphO24sASnmsRa0i1yDQow1POhV4pIHGmSXisjwbd3tzV3jtTyMYFkW4vCciDAzI4II8OBOCmAxrlc1UWTlW59UcqEwmlNA5zWTf3ZUuz_2ernI0Xf25EHWt9a3a_rHIfMhFMcLmcTeT9fP62nLw8yZh9Axqreug</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype></control><display><type>article</type><title>A class of bounded approximation algorithms for graph partitioning</title><source>Wiley Online Library Mathematics Backfiles</source><creator>Feo, Thomas A. ; Khellaf, Mallek</creator><creatorcontrib>Feo, Thomas A. ; Khellaf, Mallek</creatorcontrib><description>This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.</description><identifier>ISSN: 0028-3045</identifier><identifier>EISSN: 1097-0037</identifier><identifier>DOI: 10.1002/net.3230200205</identifier><identifier>CODEN: NTWKAA</identifier><language>eng</language><publisher>New York: Wiley Subscription Services, Inc., A Wiley Company</publisher><subject>Applied sciences ; Exact sciences and technology ; Flows in networks. Combinatorial problems ; Operational research and scientific management ; Operational research. Management science</subject><ispartof>Networks, 1990-03, Vol.20 (2), p.181-195</ispartof><rights>Copyright © 1990 Wiley Periodicals, Inc., A Wiley Company</rights><rights>1991 INIST-CNRS</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323</citedby><cites>FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktopdf>$$Uhttps://onlinelibrary.wiley.com/doi/pdf/10.1002%2Fnet.3230200205$$EPDF$$P50$$Gwiley$$H</linktopdf><linktohtml>$$Uhttps://onlinelibrary.wiley.com/doi/full/10.1002%2Fnet.3230200205$$EHTML$$P50$$Gwiley$$H</linktohtml><link.rule.ids>314,780,784,27924,27925,50859,50968</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=19762224$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>Feo, Thomas A.</creatorcontrib><creatorcontrib>Khellaf, Mallek</creatorcontrib><title>A class of bounded approximation algorithms for graph partitioning</title><title>Networks</title><addtitle>Networks</addtitle><description>This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.</description><subject>Applied sciences</subject><subject>Exact sciences and technology</subject><subject>Flows in networks. Combinatorial problems</subject><subject>Operational research and scientific management</subject><subject>Operational research. Management science</subject><issn>0028-3045</issn><issn>1097-0037</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1990</creationdate><recordtype>article</recordtype><recordid>eNqFkM9PwjAUxxujiYhePfficfjarut2RIJoJEgMBm9NWTuojm1pZ4T_3pIZiSdPL-_H573v-yJ0TWBAAOhtZdoBowxoSICfoB6BTEQATJyiXqilEYOYn6ML798BCOEk7aG7Ic5L5T2uC7yqPyttNFZN4-qd3arW1hVW5bp2tt1sPS5qh9dONRvcKNfaQ9tW60t0VqjSm6uf2Eev9-PF6CGaPk8eR8NplMeU8YilFIqE5XGqMlOQmCVqFXRSphO24sASnmsRa0i1yDQow1POhV4pIHGmSXisjwbd3tzV3jtTyMYFkW4vCciDAzI4II8OBOCmAxrlc1UWTlW59UcqEwmlNA5zWTf3ZUuz_2ernI0Xf25EHWt9a3a_rHIfMhFMcLmcTeT9fP62nLw8yZh9Axqreug</recordid><startdate>199003</startdate><enddate>199003</enddate><creator>Feo, Thomas A.</creator><creator>Khellaf, Mallek</creator><general>Wiley Subscription Services, Inc., A Wiley Company</general><general>John Wiley &amp; Sons</general><scope>BSCLL</scope><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope></search><sort><creationdate>199003</creationdate><title>A class of bounded approximation algorithms for graph partitioning</title><author>Feo, Thomas A. ; Khellaf, Mallek</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1990</creationdate><topic>Applied sciences</topic><topic>Exact sciences and technology</topic><topic>Flows in networks. Combinatorial problems</topic><topic>Operational research and scientific management</topic><topic>Operational research. Management science</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>Feo, Thomas A.</creatorcontrib><creatorcontrib>Khellaf, Mallek</creatorcontrib><collection>Istex</collection><collection>Pascal-Francis</collection><collection>CrossRef</collection><jtitle>Networks</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>Feo, Thomas A.</au><au>Khellaf, Mallek</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>A class of bounded approximation algorithms for graph partitioning</atitle><jtitle>Networks</jtitle><addtitle>Networks</addtitle><date>1990-03</date><risdate>1990</risdate><volume>20</volume><issue>2</issue><spage>181</spage><epage>195</epage><pages>181-195</pages><issn>0028-3045</issn><eissn>1097-0037</eissn><coden>NTWKAA</coden><abstract>This paper considers the problem of partitioning the nodes of a weighted graph into k disjoint subsets of bounded size, such that the sum of the weights of the edges whose end vertices belong to the same subset is maximized. A class of approximation algorithms based on matching is presented. These algorithms are shown to yield practical worst‐case bounds when k is large. Extensive empirical experimentation indicates that the methods produce consistently good solutions to an important VLSI design problem in a fraction of the time required by competing methods.</abstract><cop>New York</cop><pub>Wiley Subscription Services, Inc., A Wiley Company</pub><doi>10.1002/net.3230200205</doi><tpages>15</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0028-3045
ispartof Networks, 1990-03, Vol.20 (2), p.181-195
issn 0028-3045
1097-0037
language eng
recordid cdi_crossref_primary_10_1002_net_3230200205
source Wiley Online Library Mathematics Backfiles
subjects Applied sciences
Exact sciences and technology
Flows in networks. Combinatorial problems
Operational research and scientific management
Operational research. Management science
title A class of bounded approximation algorithms for graph partitioning
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-04T13%3A33%3A38IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-istex_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=A%20class%20of%20bounded%20approximation%20algorithms%20for%20graph%20partitioning&rft.jtitle=Networks&rft.au=Feo,%20Thomas%20A.&rft.date=1990-03&rft.volume=20&rft.issue=2&rft.spage=181&rft.epage=195&rft.pages=181-195&rft.issn=0028-3045&rft.eissn=1097-0037&rft.coden=NTWKAA&rft_id=info:doi/10.1002/net.3230200205&rft_dat=%3Cistex_cross%3Eark_67375_WNG_FPPXWGRK_4%3C/istex_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c4235-3820f63c48a9ef1436ab20523d63b50365cd74d08d79d0ae58557dba0149d1323%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rfr_iscdi=true