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

DOI10.1016/j.tcs.2007.04.030zbMath1144.68045OpenAlexW2019597617MaRDI QIDQ995565

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

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

cliquesapproximation algorithmsweighted interval graphs

Mathematics Subject Classification ID

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

Related Items

PROCESSING AN OFFLINE INSERTION-QUERY SEQUENCE WITH APPLICATIONS ⋮ Processing an Offline Insertion-Query Sequence with Applications ⋮ On the clique partitioning problem in weighted interval graphs ⋮ On the minimum clique partitioning problem on weighted chordal graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Restrictions of graph partition problems. I
• Interval graphs and maps of DNA
• On the \(k\)-coloring of intervals
• Scheduling Interval-Ordered Tasks
• Pathwidth, Bandwidth, and Completion Problems to Proper Interval Graphs with Small Cliques