Independent packings in structured graphs

• 成果类型: Article; Proceedings Paper
• 署名作者: Cameron, K; Hell, P
• 署名单位: Wilfrid Laurier University; Simon Fraser University
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-005-0649-5
• 发表日期: 2006
• 页码: 201-213
• 关键词: maximum induced matchings; comparability-graphs; parallel algorithms; sets

摘要

Packing a maximum number of disjoint triangles into a given graph G is NP-hard, even for most classes of structured graphs. In contrast, we show that packing a maximum number of independent (that is, disjoint and nonadjacent) triangles is polynomial-time solvable for many classes of structured graphs, including weakly chordal graphs, asteroidal triple-free graphs, polygon-circle graphs, and interval-filament graphs. These classes contain other well-known classes such as chordal graphs, cocomparability graphs, circle graphs, circular-arc graphs, and outerplanar graphs. Our results apply more generally to independent packings by members of any family of connected graphs.