An optimal algorithm for maximum two planar subset problem /spl lsqb/VLSI layout/spl rsqb

The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for...

Full description

Saved in:
Bibliographic Details
Main Authors: Panyam, A., Danda, S., Madhwapathy, S., Sherwani, N.
Format: Conference Proceeding
Language:English
Subjects:
Algorithm design and analysis
Approximation algorithms
Computer science
Polynomials
Routing
Very large scale integration
Online Access:Request full text
Tags: Add Tag
No Tags, Be the first to tag this record!
cited_by
cites
container_end_page 85
container_issue
container_start_page 80
container_title
container_volume
creator Panyam, A.
Danda, S.
Madhwapathy, S.
Sherwani, N.
description The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for this problem. In this paper we show that TRMPS problem can be solved optimally in polynomial time, and we present an O(kn/sup 2/) algorithm to solve this problem. Our algorithm can also be extended to solve the TRMPS problem, in the presence of pre-routed nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain an improved approximation algorithm, for over the cell routing in middle terminal model standard cell layouts.< >
doi_str_mv 10.1109/GLSV.1994.289991
format conference_proceeding
fullrecord <record><control><sourceid>ieee_6IE</sourceid><recordid>TN_cdi_ieee_primary_289991</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><ieee_id>289991</ieee_id><sourcerecordid>289991</sourcerecordid><originalsourceid>FETCH-ieee_primary_2899913</originalsourceid><addsrcrecordid>eNp9jssKwjAURAMi-OpeXN0fsM3V2jZLEV_gThFcSQpRK0kTkxTt31vUtbMZOGcxQ8gQaYhIWbTe7Y8hMhaHk4wxhi3SoxlmySxBmnZI4NydNolnyDDtktO8BG18obgELq_aFv6m4KItKP4qVKXAPzUYyUtuwVW5Ex6M1bkUCiJnJEj3yKPjbr8FyWtd-Q-0DRyQ9oVLJ4Jf98lotTwsNuNCCHE2tpm09fl7cvpXvgHHgkGI</addsrcrecordid><sourcetype>Publisher</sourcetype><iscdi>true</iscdi><recordtype>conference_proceeding</recordtype></control><display><type>conference_proceeding</type><title>An optimal algorithm for maximum two planar subset problem /spl lsqb/VLSI layout/spl rsqb</title><source>IEEE Electronic Library (IEL) Conference Proceedings</source><creator>Panyam, A. ; Danda, S. ; Madhwapathy, S. ; Sherwani, N.</creator><creatorcontrib>Panyam, A. ; Danda, S. ; Madhwapathy, S. ; Sherwani, N.</creatorcontrib><description>The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for this problem. In this paper we show that TRMPS problem can be solved optimally in polynomial time, and we present an O(kn/sup 2/) algorithm to solve this problem. Our algorithm can also be extended to solve the TRMPS problem, in the presence of pre-routed nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain an improved approximation algorithm, for over the cell routing in middle terminal model standard cell layouts.&lt; &gt;</description><identifier>ISBN: 0818656107</identifier><identifier>ISBN: 9780818656101</identifier><identifier>DOI: 10.1109/GLSV.1994.289991</identifier><language>eng</language><publisher>IEEE Comput. Soc. Press</publisher><subject>Algorithm design and analysis ; Approximation algorithms ; Computer science ; Polynomials ; Routing ; Very large scale integration</subject><ispartof>Proceedings of 4th Great Lakes Symposium on VLSI, 1994, p.80-85</ispartof><woscitedreferencessubscribed>false</woscitedreferencessubscribed></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://ieeexplore.ieee.org/document/289991$$EHTML$$P50$$Gieee$$H</linktohtml><link.rule.ids>309,310,780,784,789,790,2058,4050,4051,27925,54920</link.rule.ids><linktorsrc>$$Uhttps://ieeexplore.ieee.org/document/289991$$EView_record_in_IEEE$$FView_record_in_$$GIEEE</linktorsrc></links><search><creatorcontrib>Panyam, A.</creatorcontrib><creatorcontrib>Danda, S.</creatorcontrib><creatorcontrib>Madhwapathy, S.</creatorcontrib><creatorcontrib>Sherwani, N.</creatorcontrib><title>An optimal algorithm for maximum two planar subset problem /spl lsqb/VLSI layout/spl rsqb</title><title>Proceedings of 4th Great Lakes Symposium on VLSI</title><addtitle>GLSV</addtitle><description>The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for this problem. In this paper we show that TRMPS problem can be solved optimally in polynomial time, and we present an O(kn/sup 2/) algorithm to solve this problem. Our algorithm can also be extended to solve the TRMPS problem, in the presence of pre-routed nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain an improved approximation algorithm, for over the cell routing in middle terminal model standard cell layouts.&lt; &gt;</description><subject>Algorithm design and analysis</subject><subject>Approximation algorithms</subject><subject>Computer science</subject><subject>Polynomials</subject><subject>Routing</subject><subject>Very large scale integration</subject><isbn>0818656107</isbn><isbn>9780818656101</isbn><fulltext>true</fulltext><rsrctype>conference_proceeding</rsrctype><creationdate>1994</creationdate><recordtype>conference_proceeding</recordtype><sourceid>6IE</sourceid><recordid>eNp9jssKwjAURAMi-OpeXN0fsM3V2jZLEV_gThFcSQpRK0kTkxTt31vUtbMZOGcxQ8gQaYhIWbTe7Y8hMhaHk4wxhi3SoxlmySxBmnZI4NydNolnyDDtktO8BG18obgELq_aFv6m4KItKP4qVKXAPzUYyUtuwVW5Ex6M1bkUCiJnJEj3yKPjbr8FyWtd-Q-0DRyQ9oVLJ4Jf98lotTwsNuNCCHE2tpm09fl7cvpXvgHHgkGI</recordid><startdate>1994</startdate><enddate>1994</enddate><creator>Panyam, A.</creator><creator>Danda, S.</creator><creator>Madhwapathy, S.</creator><creator>Sherwani, N.</creator><general>IEEE Comput. Soc. Press</general><scope>6IE</scope><scope>6IL</scope><scope>CBEJK</scope><scope>RIE</scope><scope>RIL</scope></search><sort><creationdate>1994</creationdate><title>An optimal algorithm for maximum two planar subset problem /spl lsqb/VLSI layout/spl rsqb</title><author>Panyam, A. ; Danda, S. ; Madhwapathy, S. ; Sherwani, N.</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-ieee_primary_2899913</frbrgroupid><rsrctype>conference_proceedings</rsrctype><prefilter>conference_proceedings</prefilter><language>eng</language><creationdate>1994</creationdate><topic>Algorithm design and analysis</topic><topic>Approximation algorithms</topic><topic>Computer science</topic><topic>Polynomials</topic><topic>Routing</topic><topic>Very large scale integration</topic><toplevel>online_resources</toplevel><creatorcontrib>Panyam, A.</creatorcontrib><creatorcontrib>Danda, S.</creatorcontrib><creatorcontrib>Madhwapathy, S.</creatorcontrib><creatorcontrib>Sherwani, N.</creatorcontrib><collection>IEEE Electronic Library (IEL) Conference Proceedings</collection><collection>IEEE Proceedings Order Plan All Online (POP All Online) 1998-present by volume</collection><collection>IEEE Xplore All Conference Proceedings</collection><collection>IEEE/IET Electronic Library (IEL)</collection><collection>IEEE Proceedings Order Plans (POP All) 1998-Present</collection></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext_linktorsrc</fulltext></delivery><addata><au>Panyam, A.</au><au>Danda, S.</au><au>Madhwapathy, S.</au><au>Sherwani, N.</au><format>book</format><genre>proceeding</genre><ristype>CONF</ristype><atitle>An optimal algorithm for maximum two planar subset problem /spl lsqb/VLSI layout/spl rsqb</atitle><btitle>Proceedings of 4th Great Lakes Symposium on VLSI</btitle><stitle>GLSV</stitle><date>1994</date><risdate>1994</risdate><spage>80</spage><epage>85</epage><pages>80-85</pages><isbn>0818656107</isbn><isbn>9780818656101</isbn><abstract>The Two Row Maximum Planar Subset (TRMPS) problem asks for finding the maximum planar subset of nets, that can be routed between two rows of terminals an a cell row. This problem was first encountered by Gong, Liu, and Preas (1990). They declared it open, and presented an approximation algorithm for this problem. In this paper we show that TRMPS problem can be solved optimally in polynomial time, and we present an O(kn/sup 2/) algorithm to solve this problem. Our algorithm can also be extended to solve the TRMPS problem, in the presence of pre-routed nets, a chosen subset of nets, as well as for planar channel routing. We also apply our technique to obtain an improved approximation algorithm, for over the cell routing in middle terminal model standard cell layouts.&lt; &gt;</abstract><pub>IEEE Comput. Soc. Press</pub><doi>10.1109/GLSV.1994.289991</doi></addata></record>
fulltext fulltext_linktorsrc
identifier ISBN: 0818656107
ispartof Proceedings of 4th Great Lakes Symposium on VLSI, 1994, p.80-85
issn
language eng
recordid cdi_ieee_primary_289991
source IEEE Electronic Library (IEL) Conference Proceedings
subjects Algorithm design and analysis
Approximation algorithms
Computer science
Polynomials
Routing
Very large scale integration
title An optimal algorithm for maximum two planar subset problem /spl lsqb/VLSI layout/spl rsqb
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-07T15%3A38%3A31IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-ieee_6IE&rft_val_fmt=info:ofi/fmt:kev:mtx:book&rft.genre=proceeding&rft.atitle=An%20optimal%20algorithm%20for%20maximum%20two%20planar%20subset%20problem%20/spl%20lsqb/VLSI%20layout/spl%20rsqb&rft.btitle=Proceedings%20of%204th%20Great%20Lakes%20Symposium%20on%20VLSI&rft.au=Panyam,%20A.&rft.date=1994&rft.spage=80&rft.epage=85&rft.pages=80-85&rft.isbn=0818656107&rft.isbn_list=9780818656101&rft_id=info:doi/10.1109/GLSV.1994.289991&rft_dat=%3Cieee_6IE%3E289991%3C/ieee_6IE%3E%3Cgrp_id%3Ecdi_FETCH-ieee_primary_2899913%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_id=info:pmid/&rft_ieee_id=289991&rfr_iscdi=true