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

DOI10.1016/J.ENDM.2006.08.020MaRDI QIDQ3439650zbMATH OpenOpenAlexFDO

Authors 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 programminginterval graphmatrix representationpolynomial algorithmproper interval graph

Mathematics Subject Classification ID

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

Recommendations

• A matrix characterization of interval and proper interval graphs
• The maximum clique problem in multiple interval graphs (extended abstract)
• Clustering and domination in perfect graphs
• Cluster deletion on interval graphs and split related graphs
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs

Cites work

• A constant approximation algorithm for the densest \(k\)-subgraph problem on chordal graphs
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• Clustering and domination in perfect graphs
• Deferred-query—An efficient approach for problems on interval and circular-arc graphs
• Efficient algorithms for interval graphs and circular-arc graphs
• scientific article; zbMATH DE number 1303554 (Why is no real title available?)
• scientific article; zbMATH DE number 512914 (Why is no real title available?)
• scientific article; zbMATH DE number 2011857 (Why is no real title available?)
• scientific article; zbMATH DE number 2117210 (Why is no real title available?)
• Simple linear time recognition of unit interval graphs

Cited in

(5)

• On the m-clique free interval subgraphs polytope: polyhedral analysis and applications
• Sitting closer to friends than enemies, revisited
• A matrix characterization of interval and proper interval graphs
• A polynomial-time algorithm for the maximum cardinality cut problem in proper interval graphs
• The maximum clique problem in multiple interval graphs (extended abstract)

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

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