Some approximation algorithms for the clique partition problem in weighted interval graphs

DOI10.1016/J.TCS.2007.04.030zbMATH Open1144.68045OpenAlexW2019597617MaRDI QIDQ995565FDOQ995565

Authors Mingxia Chen, Jianbo Li, Jianping Li, Weidong Li, Lusheng Wang

Publication date 3 September 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.04.030

zbMATH Keywords

approximation algorithmscliquesweighted interval graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) Combinatorial optimization (90C27) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25) Graph representations (geometric and intersection representations, etc.) (05C62) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Recommendations

• Minimum Clique Partition Problem with Constrained Weight for Interval Graphs
• On the clique partitioning problem in weighted interval graphs
• On the minimum clique partitioning problem on weighted chordal graphs
• The maximum clique problem in multiple interval graphs
• Clique Clustering Yields a PTAS for max-Coloring Interval Graphs

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3936534 (Why is no real title available?)
• scientific article; zbMATH DE number 3706451 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Interval graphs and maps of DNA
• On the \(k\)-coloring of intervals
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques
• Restrictions of graph partition problems. I
• Scheduling Interval-Ordered Tasks

Cited in

(11)

• Minimum Clique Partition Problem with Constrained Weight for Interval Graphs
• Processing an offline insertion-query sequence with applications
• Processing an Offline Insertion-Query Sequence with Applications
• A parllel algorithm for finding a maximum weight clique of an interval graph
• A simple approximation algorithm for WIS based on the approximability in \(k\)-partite graphs
• On the approximability of the minimum weight \(t\)-partite clique problem
• On the minimum clique partitioning problem on weighted chordal graphs
• scientific article; zbMATH DE number 7764108 (Why is no real title available?)
• On the clique partitioning problem in weighted interval graphs
• Clique partitioning of interval graphs with submodular costs on the cliques
• Two-way and multiway partitioning of a set of intervals for clique-width maximization

This page was built for publication: Some approximation algorithms for the clique partition problem in weighted interval graphs

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