Decomposing a set of points into chains, with applications to permutation and circle graphs

DOI10.1016/0020-0190(85)90093-6zbMath0586.68034OpenAlexW2061944694MaRDI QIDQ1071505

Kenneth J. Supowit

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

zbMATH Keywords

graph coloringanalysis of algorithmscomputational geometrypermutation graphscircle graphscoloring algorithmascending chainspartition algorithm

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15)

Related Items (13)

Coloring permutation graphs in parallel ⋮ A theorem on permutation graphs with applications ⋮ Compressed spaced suffix arrays ⋮ Efficient approximation algorithms for domatic partition and on-line coloring of circular arc graphs ⋮ An \(\Omega\) (n log n) lower bound for decomposing a set of points into chains ⋮ Generate all maximal independent sets in permutation graphs ⋮ Efficient algorithms for the minimum weighted dominating clique problem on permutation graphs ⋮ A tutorial on the use of graph coloring for some problems in robotics ⋮ The weighted maximum independent set problem in permutation graphs ⋮ Untangled monotonic chains and adaptive range search ⋮ Heuristic methods and applications: A categorized survey ⋮ Fully dynamic algorithms for permutation graph coloring ⋮ Parallel algorithms for permutation graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Approximation algorithms for combinatorial problems
• A decomposition theorem for partially ordered sets
• On Comparability and Permutation Graphs
• Improving the performance guarantee for approximate graph coloring
• Permutation Graphs and Transitive Graphs

This page was built for publication: Decomposing a set of points into chains, with applications to permutation and circle graphs