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

DOI10.1016/J.IPL.2015.12.001zbMATH Open1357.05115OpenAlexW2212285143MaRDI QIDQ264186FDOQ264186

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

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

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)

Cites Work

• 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
• Title not available (Why is that?)
• A simple polynomial algorithm for the longest path problem on cocomparability graphs
• Nonoverlapping local alignments (weighted independent sets of axis-parallel rectangles)

Cited In (9)

• Maximum bipartite subgraphs of geometric intersection graphs
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• On the power of graph searching for cocomparability graphs
• The LexCycle on $\overline{P_{2}\cup P_{3}}$-free 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
• A new graph parameter to measure linearity

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)