An approximation algorithm for clustering graphs with dominating diametral path

DOI10.1016/S0020-0190(97)81663-8zbMath1337.68290OpenAlexW2073927206MaRDI QIDQ290198

Jitender S. 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

design of algorithmsapproximation algorithmsgraph clusteringspecial graph classes

Mathematics Subject Classification ID

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

Related Items

Treewidth for graphs with small chordality, Algorithms for graphs with small octopus, A clustering method to identify representative financial ratios, Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms, Exact algorithms for the minimum \(s\)-club partitioning problem, Evaluating financial performance of Taiwan container shipping companies by strength and weakness indices

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• The ellipsoid method and its consequences in combinatorial optimization
• Low diameter graph decompositions
• Doubly lexical ordering of dense 0--1 matrices
• Organization of clustered files for consecutive retrieval
• Three Partition Refinement Algorithms
• Partitioning trees: Matching, domination, and maximum diameter
• 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