Decomposing a set of points into chains, with applications to permutation and circle graphs
From MaRDI portal
Publication:1071505
DOI10.1016/0020-0190(85)90093-6zbMath0586.68034MaRDI QIDQ1071505
Publication date: 1985
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(85)90093-6
graph coloring; analysis of algorithms; computational geometry; permutation graphs; circle graphs; coloring algorithm; ascending chains; partition algorithm
68Q25: Analysis of algorithms and problem complexity
68R10: Graph theory (including graph drawing) in computer science
05C15: Coloring of graphs and hypergraphs
Related Items
Generate all maximal independent sets in permutation graphs, Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs, The weighted maximum independent set problem in permutation graphs, Parallel algorithms for permutation graphs, A theorem on permutation graphs with applications, Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs, Fully dynamic algorithms for permutation graph coloring