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

DOI10.1016/J.IPL.2015.12.001MaRDI QIDQ264186zbMATHOpenAlexFDO

Authors 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

cocomparability graphsmaximum weight independent setminimum weight vertex coverposets

Mathematics Subject Classification ID

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

Recommendations

• Weighted independent perfect domination on cocomparability graphs
• Algorithms and Computation
• An efficient algorithm for finding a maximum weight 2-independent set on interval graphs
• A faster algorithm for maximum independent set on interval filament graphs
• The weighted maximum independent set problem in permutation graphs

Cites work

• scientific article; zbMATH DE number 1753166 (Why is no real title available?)
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Algorithmic graph theory and perfect graphs
• Combinatorial auctions: a survey
• Domination on Cocomparability Graphs
• LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
• Minimum feedback vertex sets in cocomparability graphs and complex bipartite graphs
• Modular decomposition and transitive orientation
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)
• Scheduling jobs with fixed start and end times

Cited in

(9)

• The LexCycle on \(\overline{P_2\cup P_3} \)-free cocomparability graphs
• Maximum bipartite subgraphs of geometric intersection graphs
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• A faster algorithm for maximum independent set on interval filament graphs
• On the power of graph searching for cocomparability graphs
• Graphs with at most two moplexes
• Maximum induced matching algorithms via vertex ordering characterizations
• On the kernel and related problems in interval digraphs
• Maximum induced matching algorithms via vertex ordering characterizations

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

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