Efficient algorithms for the maximum weight clique and maximum weight independent set problems on permutation graphs
From MaRDI portal
Publication:1195486
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
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)
Related Items
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
