Clustering bipartite and chordal graphs: Complexity, sequential and parallel algorithms

DOI10.1016/S0166-218X(98)00094-8zbMath0927.68065MaRDI QIDQ1283779

Nesrine Abbas, Lorna K. Stewart

Publication date: 31 May 1999

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

chordal graphsclustering problems

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Algorithms for graphs with small octopus ⋮ Exact algorithms for the minimum \(s\)-club partitioning problem

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An approximation algorithm for clustering graphs with dominating diametral path
• Domination, independent domination, and duality in strongly chordal graphs
• Characterizations of strongly chordal graphs
• Bipartite permutation graphs
• Some parallel algorithms on interval graphs
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Low diameter graph decompositions
• Circuit partitioning with size and connection constraints
• Partitioning trees: Matching, domination, and maximum diameter
• Efficient algorithms for interval graphs and circular-arc graphs
• Maximum matching in a convex bipartite graph