Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs

DOI10.1016/0020-0190(92)90114-BzbMath0768.68126OpenAlexW2056944493MaRDI QIDQ1195486

Fu-Hsing Wang, Maw-Shang Chang

Publication date: 29 November 1992

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(92)90114-b

zbMATH Keywords

efficient algorithmspermutation graphsoverlap graphclique independent setweight independent set

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Related Items (14)

Pattern matching for permutations ⋮ Longest increasing subsequences in sliding windows ⋮ A fast algorithm for permutation pattern matching based on alternating runs ⋮ On the distribution of the number of occurrences of an order-preserving pattern of length three in a random permutation ⋮ A linear time algorithm for consecutive permutation pattern matching ⋮ On the longest upsequence problem for permutations ⋮ Pattern matching for permutations ⋮ A parallel algorithm to generate all maximal independent sets on permutation graphs ⋮ Finding common structured patterns in linear graphs ⋮ Fixed-parameter tractability results for feedback set problems in tournaments ⋮ Finding and counting permutations via CSPs ⋮ Maximum weightk-independent set problem on permutation graphs ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ An efficient algorithm to generate all maximal independent sets on trapezoid graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding a maximum independent set in a permutation graph
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
• On Comparability and Permutation Graphs
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Permutation Graphs and Transitive Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph

This page was built for publication: Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs