Coloring permutation graphs in parallel

DOI10.1016/S0166-218X(01)00289-XMaRDI QIDQ1613373zbMATH OpenFDO

Authors Stavros D. Nikolopoulos

Publication date 29 August 2002

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

Full work available at URL https://doi.org/10.1016/S0166-218X(01)00289-X

zbMATH Keywords

coloringcoloring permutation graphscoloring-permutation treeCREW PRAM model

Mathematics Subject Classification ID

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

Recommendations

• Coloring permutation graphs in parallel
• scientific article; zbMATH DE number 1436135
• Parallel algorithms for permutation graphs
• scientific article; zbMATH DE number 17674
• Efficient parallel algorithms for permutation graphs

Cites work

• 25 pretty graph colouring problems
• A New Algorithm for Generating All the Maximal Independent Sets
• Bipartite permutation graphs
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Domination in permutation graphs
• Fast algorithms for generating all maximal independent sets of interval, circular-arc and chordal graphs
• Finding a minimum independent dominating set in a permutation graph
• Generate all maximal independent sets in permutation graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 4147494 (Why is no real title available?)
• scientific article; zbMATH DE number 3965452 (Why is no real title available?)
• scientific article; zbMATH DE number 88968 (Why is no real title available?)
• scientific article; zbMATH DE number 107951 (Why is no real title available?)
• scientific article; zbMATH DE number 815575 (Why is no real title available?)
• scientific article; zbMATH DE number 1436135 (Why is no real title available?)
• On Comparability and Permutation Graphs
• On domination problems for permutation and other graphs
• On the performance of the first-fit coloring algorithm on permutation graphs
• Optimal bounds for decision problems on the CRCW PRAM
• Parallel algorithms for permutation graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(4)

• Parallel algorithms for permutation graphs
• Coloring permutation graphs in parallel
• scientific article; zbMATH DE number 1436135 (Why is no real title available?)
• A compact data structure and parallel algorithms for permutation graphs

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1613373)