Coloring permutation graphs in parallel

DOI10.1016/S0166-218X(01)00289-XzbMath1002.68514MaRDI QIDQ1613373

Stavros D. Nikolopoulos

Publication date: 29 August 2002

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

coloring; CREW PRAM model; coloring permutation graphs; coloring-permutation tree

Mathematics Subject Classification ID

68R10: Graph theory (including graph drawing) in computer science

05C15: Coloring of graphs and hypergraphs

05C17: Perfect graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the performance of the first-fit coloring algorithm on permutation graphs
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Bipartite permutation graphs
• On domination problems for permutation and other graphs
• Finding a minimum independent dominating set in a permutation graph
• Parallel algorithms for permutation graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• On Comparability and Permutation Graphs
• Domination in permutation graphs
• A New Algorithm for Generating All the Maximal Independent Sets
• Generate all maximal independent sets in permutation graphs
• Optimal bounds for decision problems on the CRCW PRAM
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• 25 pretty graph colouring problems