An approximation algorithm for clustering graphs with dominating diametral path

DOI10.1016/S0020-0190(97)81663-8MaRDI QIDQ290198zbMATHOpenAlexFDO

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

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)

Recommendations

• Publication:2721983
• 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

Cites work

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

Cited in

(10)

• A clustering method to identify representative financial ratios
• A 2-approximation algorithm for the graph 2-clustering problem
• 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
• Finding dominating cliques efficiently, in strongly chordal graphs and undirected path graphs
• Dynamic Digraph Connectivity Hastens Minimum Sum-of-Diameters Clustering
• Algorithms for graphs with small octopus
• Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms
• Algorithms for Cluster Busting in Anchored Graph Drawing

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)