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

DOI10.1016/0020-0190(92)90114-BzbMATH Open0768.68126OpenAlexW2056944493MaRDI QIDQ1195486FDOQ1195486

Authors: 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

overlap graphefficient algorithmspermutation graphsclique independent setweight independent set

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Transitive Orientation of Graphs and Identification of Permutation Graphs
• Finding a maximum independent set in a permutation graph
• Permutation Graphs and Transitive Graphs
• On Comparability and Permutation Graphs
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs

Cited In (14)

• Maximum weightk-independent set problem on permutation graphs
• A parallel algorithm to generate all maximal independent sets on permutation graphs
• Finding common structured patterns in linear graphs
• Pattern matching for permutations
• Pattern matching for permutations
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• A linear time algorithm for consecutive permutation pattern matching
• Finding and counting permutations via CSPs
• On the distribution of the number of occurrences of an order-preserving pattern of length three in a random permutation
• Longest increasing subsequences in sliding windows
• An efficient PRAM algorithm for maximum-weight independent set on permutation graphs
• On the longest upsequence problem for permutations
• Fixed-parameter tractability results for feedback set problems in tournaments

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

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