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!
Description
Summary: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.
ISSN:0020-0190
1872-6119
DOI:10.1016/0020-0190(88)90090-7