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

coloringCREW PRAM modelcoloring permutation graphscoloring-permutation tree

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)

Cites Work

• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Coloring permutation graphs in parallel