A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs

DOI10.1016/j.ipl.2015.12.001zbMath1357.05115OpenAlexW2212285143MaRDI QIDQ264186

Ekkehard Köhler, Lalla Mouatadid

Publication date: 6 April 2016

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

Full work available at URL: https://doi.org/10.1016/j.ipl.2015.12.001

zbMATH Keywords

posetscocomparability graphsmaximum weight independent setminimum weight vertex cover

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Signed and weighted graphs (05C22)

Related Items (7)

The LexCycle on $\overline{P_{2}\cup P_{3}}$-free Cocomparability Graphs ⋮ On the kernel and related problems in interval digraphs ⋮ A new graph parameter to measure linearity ⋮ Maximum induced matching algorithms via vertex ordering characterizations ⋮ On the Power of Graph Searching for Cocomparability Graphs ⋮ Maximum Induced Matching Algorithms via Vertex Ordering Characterizations ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

Cites Work

• Unnamed Item
• Scheduling jobs with fixed start and end times
• Modular decomposition and transitive orientation
• Algorithmic graph theory and perfect graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• LDFS-Based Certifying Algorithm for the Minimum Path Cover Problem on Cocomparability Graphs
• Combinatorial Auctions: A Survey
• Domination on Cocomparability Graphs
• A Simple Polynomial Algorithm for the Longest Path Problem on Cocomparability Graphs
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

This page was built for publication: A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs