An approximation algorithm for clustering graphs with dominating diametral path

DOI10.1016/S0020-0190(97)81663-8zbMATH Open1337.68290OpenAlexW2073927206MaRDI QIDQ290198FDOQ290198

Authors: Jitender Deogun, Dieter Kratsch, George Steiner 

Publication date: 1 June 2016

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0020-0190(97)81663-8

Recommendations

• scientific article; zbMATH DE number 1617263
• Approximation algorithms for clustering to minimize the sum of diameters
• Approximation algorithms for min-sum \(p\)-clustering
• Graph clustering with a constraint on cluster sizes
• Clustering to minimize the maximum intercluster distance

zbMATH Keywords

graph clusteringapproximation algorithmsdesign of algorithmsspecial graph classes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• The ellipsoid method and its consequences in combinatorial optimization
• Doubly lexical ordering of dense 0--1 matrices
• Three Partition Refinement Algorithms
• Title not available (Why is that?)
• Characterizations of strongly chordal graphs
• Low diameter graph decompositions
• Organization of clustered files for consecutive retrieval
• Partitioning trees: Matching, domination, and maximum diameter
• Title not available (Why is that?)
• Linear time algorithms for dominating pairs in asteroidal triple-free graphs
• On the hardness of approximating minimization problems
• Cluster Analysis and Mathematical Programming
• The NP-completeness column: An ongoing guide
• Domination, independent domination, and duality in strongly chordal graphs

Cited In (10)

• Dynamic Digraph Connectivity Hastens Minimum Sum-of-Diameters Clustering
• Treewidth for graphs with small chordality
• Evaluating financial performance of Taiwan container shipping companies by strength and weakness indices
• Exact algorithms for the minimum \(s\)-club partitioning problem
• Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
• Algorithms for graphs with small octopus
• Algorithms for Cluster Busting in Anchored Graph Drawing
• A 2-approximation algorithm for the graph 2-clustering problem
• A clustering method to identify representative financial ratios
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs

This page was built for publication: An approximation algorithm for clustering graphs with dominating diametral path

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q290198)