A polynomial algorithm for the k-cluster problem on the interval graphs

DOI10.1016/j.endm.2006.08.020zbMath1225.05184OpenAlexW2014290730MaRDI QIDQ3439650

George B. Mertzios

Publication date: 29 May 2007

Published in: Electronic Notes in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.endm.2006.08.020

zbMATH Keywords

dynamic programmingmatrix representationpolynomial algorithminterval graphproper interval graph

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Graph representations (geometric and intersection representations, etc.) (05C62)

Related Items (2)

A matrix characterization of interval and proper interval graphs ⋮ Sitting closer to friends than enemies, revisited

Cites Work

• Simple linear time recognition of unit interval graphs
• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• Clustering and domination in perfect graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: A polynomial algorithm for the k-cluster problem on the interval graphs