Parallel algorithms for permutation graphs

DOI10.1007/BF01990525MaRDI QIDQ1314630zbMATH OpenOpenAlexFDO

Authors Gen-Huey Chen, C. W. Yu

Publication date 7 March 1994

Published in BIT (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01990525

zbMATH Keywords

parallel algorithmspermutation graphs

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Recommendations

• scientific article; zbMATH DE number 1436135
• Coloring permutation graphs in parallel
• Efficient parallel algorithms for permutation graphs
• Coloring permutation graphs in parallel
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs

Cites work

• Algorithms for the Longest Common Subsequence Problem
• Bipartite permutation graphs
• Cascading Divide-and-Conquer: A Technique for Designing Parallel Algorithms
• Decomposing a set of points into chains, with applications to permutation and circle graphs
• Domination in permutation graphs
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3965452 (Why is no real title available?)
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• On Comparability and Permutation Graphs
• On rectangular visibility
• Scanline algorithms on a grid
• Transitive Orientation of Graphs and Identification of Permutation Graphs

Cited in

(24)

• The weighted maximum independent set problem in permutation graphs
• Sequential and parallel algorithms for the maximum-weight independent set problem on permutation graphs
• An NC algorithm for the clique cover problem in cocomparability graphs and its application
• Coloring permutation graphs in parallel
• Parallel algorithms for separable permutations
• Efficient parallel algorithms for permutation graphs
• The minimum weight dominating set problem for permutation graphs is in NC
• On the complexity of cell flipping in permutation diagrams and multiprocessor scheduling problems
• Coloring permutation graphs in parallel
• A parallel algorithm for solving the coloring problem on trapezoid graphs
• Fully dynamic algorithms for permutation graph coloring
• Parallel algorithms for parity graphs
• scientific article; zbMATH DE number 4147494 (Why is no real title available?)
• scientific article; zbMATH DE number 5307920 (Why is no real title available?)
• scientific article; zbMATH DE number 4049080 (Why is no real title available?)
• scientific article; zbMATH DE number 1230492 (Why is no real title available?)
• Some Efficient Algorithms for Permutation Graphs
• scientific article; zbMATH DE number 4115994 (Why is no real title available?)
• Parallel algorithms for P4-comparability graphs
• An optimal parallel algorithm to compute all cutvertices and blocks on permutation graphs
• scientific article; zbMATH DE number 1436135 (Why is no real title available?)
• Efficient parallel algorithms for bipartite permutation graphs
• A permutation parallel algorithm under exchange restriction with message passing interface
• A compact data structure and parallel algorithms for permutation graphs

This page was built for publication: Parallel algorithms for permutation graphs

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