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

DOI10.1016/0020-0190(92)90114-BMaRDI QIDQ1195486zbMATH OpenOpenAlexFDO

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

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Algorithms for a maximum clique and a maximum independent set of a circle graph
• 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
• Permutation Graphs and Transitive Graphs
• Transitive Orientation of Graphs and Identification of Permutation 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
• Efficient algorithms with performance guarantees for some problems of finding several discrete disjoint subgraphs in complete weighted graph
• Pattern matching for permutations
• A linear time algorithm for consecutive permutation pattern matching
• An efficient algorithm to generate all maximal independent sets on trapezoid graphs
• 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)