The complexity of ultrametric partitions on graphs

Partitioning of graphs has many practical applications namely in cluster analysis and in automated design of VLSI circuits. Using 1-1 correspondence between ultrametric partitions of a weighted complete graph K( w) on a finite set X and ultrametrics on X, the computational complexity of the approxim...

Full description

Saved in:
Bibliographic Details
Published in:Information processing letters 1988-04, Vol.27 (5), p.265-270
Main Author: KRIVANEK, M
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Cluster analysis
Computer science
control theory
systems
Decision analysis
Exact sciences and technology
Information retrieval. Graph
Mathematical analysis
NP-completeness
polynomial algorithm
Theoretical computing
Ultrametric partition
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-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313
cites cdi_FETCH-LOGICAL-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313
container_end_page 270
container_issue 5
container_start_page 265
container_title Information processing letters
container_volume 27
creator KRIVANEK, M
description Partitioning of graphs has many practical applications namely in cluster analysis and in automated design of VLSI circuits. Using 1-1 correspondence between ultrametric partitions of a weighted complete graph K( w) on a finite set X and ultrametrics on X, the computational complexity of the approximation of w by means of an ultrametric u is investigated and systematized. As a main result, a polynomial algorithm that solves the problem under some ‘min-max’ criterion is developed.
doi_str_mv 10.1016/0020-0190(88)90090-7
format article
fullrecord <record><control><sourceid>proquest_cross</sourceid><recordid>TN_cdi_proquest_miscellaneous_25070700</recordid><sourceformat>XML</sourceformat><sourcesystem>PC</sourcesystem><els_id>0020019088900907</els_id><sourcerecordid>25070700</sourcerecordid><originalsourceid>FETCH-LOGICAL-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313</originalsourceid><addsrcrecordid>eNp9kE1LxDAQhoMouK7-Aw9FRPRQnSRNk1wEWfyCBS_rOaRp6mZpm5q04v57u-6yBw8yh7k87zvDg9A5hlsMOL8DIJAClnAtxI0EkJDyAzTBgpM0x1geoskeOUYnMa4AIM8onyCyWNrE-Kar7bfr14mvkqHug25sH5xJOh161zvfxsS3yUfQ3TKeoqNK19Ge7fYUvT89LmYv6fzt-XX2ME8NlbhPGeVZXlBgLNeiKvIyKzDhOZMZM0xWhSXU8qqoOM6g0JaVjBhGsCRacCMpplN0te3tgv8cbOxV46Kxda1b64eoCAM-DozgxR9w5YfQjr8pQjnhgnAyQtkWMsHHGGyluuAaHdYKg9pYVBtFaqNICaF-LSo-xi533ToaXVdBt8bFfZYDFpLQEbvfYnYU8uVsUNE42xpbumBNr0rv_r_zA-Mgg3U</addsrcrecordid><sourcetype>Aggregation Database</sourcetype><iscdi>true</iscdi><recordtype>article</recordtype><pqid>237278272</pqid></control><display><type>article</type><title>The complexity of ultrametric partitions on graphs</title><source>ScienceDirect: Mathematics Backfile</source><source>ScienceDirect Journals</source><creator>KRIVANEK, M</creator><creatorcontrib>KRIVANEK, M</creatorcontrib><description>Partitioning of graphs has many practical applications namely in cluster analysis and in automated design of VLSI circuits. Using 1-1 correspondence between ultrametric partitions of a weighted complete graph K( w) on a finite set X and ultrametrics on X, the computational complexity of the approximation of w by means of an ultrametric u is investigated and systematized. As a main result, a polynomial algorithm that solves the problem under some ‘min-max’ criterion is developed.</description><identifier>ISSN: 0020-0190</identifier><identifier>EISSN: 1872-6119</identifier><identifier>DOI: 10.1016/0020-0190(88)90090-7</identifier><identifier>CODEN: IFPLAT</identifier><language>eng</language><publisher>Amsterdam: Elsevier B.V</publisher><subject>Algorithms ; Applied sciences ; Cluster analysis ; Computer science; control theory; systems ; Decision analysis ; Exact sciences and technology ; Information retrieval. Graph ; Mathematical analysis ; NP-completeness ; polynomial algorithm ; Theoretical computing ; Ultrametric partition</subject><ispartof>Information processing letters, 1988-04, Vol.27 (5), p.265-270</ispartof><rights>1988</rights><rights>1989 INIST-CNRS</rights><rights>Copyright Elsevier Sequoia S.A. Apr 28, 1988</rights><lds50>peer_reviewed</lds50><woscitedreferencessubscribed>false</woscitedreferencessubscribed><citedby>FETCH-LOGICAL-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313</citedby><cites>FETCH-LOGICAL-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313</cites></display><links><openurl>$$Topenurl_article</openurl><openurlfulltext>$$Topenurlfull_article</openurlfulltext><thumbnail>$$Tsyndetics_thumb_exl</thumbnail><linktohtml>$$Uhttps://www.sciencedirect.com/science/article/pii/0020019088900907$$EHTML$$P50$$Gelsevier$$H</linktohtml><link.rule.ids>314,776,780,3416,3551,27903,27904,45951,45981</link.rule.ids><backlink>$$Uhttp://pascal-francis.inist.fr/vibad/index.php?action=getRecordDetail&amp;idt=7018923$$DView record in Pascal Francis$$Hfree_for_read</backlink></links><search><creatorcontrib>KRIVANEK, M</creatorcontrib><title>The complexity of ultrametric partitions on graphs</title><title>Information processing letters</title><description>Partitioning of graphs has many practical applications namely in cluster analysis and in automated design of VLSI circuits. Using 1-1 correspondence between ultrametric partitions of a weighted complete graph K( w) on a finite set X and ultrametrics on X, the computational complexity of the approximation of w by means of an ultrametric u is investigated and systematized. As a main result, a polynomial algorithm that solves the problem under some ‘min-max’ criterion is developed.</description><subject>Algorithms</subject><subject>Applied sciences</subject><subject>Cluster analysis</subject><subject>Computer science; control theory; systems</subject><subject>Decision analysis</subject><subject>Exact sciences and technology</subject><subject>Information retrieval. Graph</subject><subject>Mathematical analysis</subject><subject>NP-completeness</subject><subject>polynomial algorithm</subject><subject>Theoretical computing</subject><subject>Ultrametric partition</subject><issn>0020-0190</issn><issn>1872-6119</issn><fulltext>true</fulltext><rsrctype>article</rsrctype><creationdate>1988</creationdate><recordtype>article</recordtype><recordid>eNp9kE1LxDAQhoMouK7-Aw9FRPRQnSRNk1wEWfyCBS_rOaRp6mZpm5q04v57u-6yBw8yh7k87zvDg9A5hlsMOL8DIJAClnAtxI0EkJDyAzTBgpM0x1geoskeOUYnMa4AIM8onyCyWNrE-Kar7bfr14mvkqHug25sH5xJOh161zvfxsS3yUfQ3TKeoqNK19Ge7fYUvT89LmYv6fzt-XX2ME8NlbhPGeVZXlBgLNeiKvIyKzDhOZMZM0xWhSXU8qqoOM6g0JaVjBhGsCRacCMpplN0te3tgv8cbOxV46Kxda1b64eoCAM-DozgxR9w5YfQjr8pQjnhgnAyQtkWMsHHGGyluuAaHdYKg9pYVBtFaqNICaF-LSo-xi533ToaXVdBt8bFfZYDFpLQEbvfYnYU8uVsUNE42xpbumBNr0rv_r_zA-Mgg3U</recordid><startdate>19880428</startdate><enddate>19880428</enddate><creator>KRIVANEK, M</creator><general>Elsevier B.V</general><general>Elsevier Science</general><general>Elsevier Sequoia S.A</general><scope>IQODW</scope><scope>AAYXX</scope><scope>CITATION</scope><scope>7SC</scope><scope>8FD</scope><scope>JQ2</scope><scope>L7M</scope><scope>L~C</scope><scope>L~D</scope></search><sort><creationdate>19880428</creationdate><title>The complexity of ultrametric partitions on graphs</title><author>KRIVANEK, M</author></sort><facets><frbrtype>5</frbrtype><frbrgroupid>cdi_FETCH-LOGICAL-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313</frbrgroupid><rsrctype>articles</rsrctype><prefilter>articles</prefilter><language>eng</language><creationdate>1988</creationdate><topic>Algorithms</topic><topic>Applied sciences</topic><topic>Cluster analysis</topic><topic>Computer science; control theory; systems</topic><topic>Decision analysis</topic><topic>Exact sciences and technology</topic><topic>Information retrieval. Graph</topic><topic>Mathematical analysis</topic><topic>NP-completeness</topic><topic>polynomial algorithm</topic><topic>Theoretical computing</topic><topic>Ultrametric partition</topic><toplevel>peer_reviewed</toplevel><toplevel>online_resources</toplevel><creatorcontrib>KRIVANEK, M</creatorcontrib><collection>Pascal-Francis</collection><collection>CrossRef</collection><collection>Computer and Information Systems Abstracts</collection><collection>Technology Research Database</collection><collection>ProQuest Computer Science Collection</collection><collection>Advanced Technologies Database with Aerospace</collection><collection>Computer and Information Systems Abstracts – Academic</collection><collection>Computer and Information Systems Abstracts Professional</collection><jtitle>Information processing letters</jtitle></facets><delivery><delcategory>Remote Search Resource</delcategory><fulltext>fulltext</fulltext></delivery><addata><au>KRIVANEK, M</au><format>journal</format><genre>article</genre><ristype>JOUR</ristype><atitle>The complexity of ultrametric partitions on graphs</atitle><jtitle>Information processing letters</jtitle><date>1988-04-28</date><risdate>1988</risdate><volume>27</volume><issue>5</issue><spage>265</spage><epage>270</epage><pages>265-270</pages><issn>0020-0190</issn><eissn>1872-6119</eissn><coden>IFPLAT</coden><abstract>Partitioning of graphs has many practical applications namely in cluster analysis and in automated design of VLSI circuits. Using 1-1 correspondence between ultrametric partitions of a weighted complete graph K( w) on a finite set X and ultrametrics on X, the computational complexity of the approximation of w by means of an ultrametric u is investigated and systematized. As a main result, a polynomial algorithm that solves the problem under some ‘min-max’ criterion is developed.</abstract><cop>Amsterdam</cop><pub>Elsevier B.V</pub><doi>10.1016/0020-0190(88)90090-7</doi><tpages>6</tpages></addata></record>
fulltext fulltext
identifier ISSN: 0020-0190
ispartof Information processing letters, 1988-04, Vol.27 (5), p.265-270
issn 0020-0190
1872-6119
language eng
recordid cdi_proquest_miscellaneous_25070700
source ScienceDirect: Mathematics Backfile; ScienceDirect Journals
subjects Algorithms
Applied sciences
Cluster analysis
Computer science
control theory
systems
Decision analysis
Exact sciences and technology
Information retrieval. Graph
Mathematical analysis
NP-completeness
polynomial algorithm
Theoretical computing
Ultrametric partition
title The complexity of ultrametric partitions on graphs
url http://sfxeu10.hosted.exlibrisgroup.com/loughborough?ctx_ver=Z39.88-2004&ctx_enc=info:ofi/enc:UTF-8&ctx_tim=2025-01-27T10%3A54%3A29IST&url_ver=Z39.88-2004&url_ctx_fmt=infofi/fmt:kev:mtx:ctx&rfr_id=info:sid/primo.exlibrisgroup.com:primo3-Article-proquest_cross&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rft.genre=article&rft.atitle=The%20complexity%20of%20ultrametric%20partitions%20on%20graphs&rft.jtitle=Information%20processing%20letters&rft.au=KRIVANEK,%20M&rft.date=1988-04-28&rft.volume=27&rft.issue=5&rft.spage=265&rft.epage=270&rft.pages=265-270&rft.issn=0020-0190&rft.eissn=1872-6119&rft.coden=IFPLAT&rft_id=info:doi/10.1016/0020-0190(88)90090-7&rft_dat=%3Cproquest_cross%3E25070700%3C/proquest_cross%3E%3Cgrp_id%3Ecdi_FETCH-LOGICAL-c391t-53746b30556a8fb6d4b12765945c59fbe23e7fbf7140bae5d52c52192a87c9313%3C/grp_id%3E%3Coa%3E%3C/oa%3E%3Curl%3E%3C/url%3E&rft_id=info:oai/&rft_pqid=237278272&rft_id=info:pmid/&rfr_iscdi=true