An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs

DOI10.1023/A:1008791627588zbMath0963.90065OpenAlexW1581220960MaRDI QIDQ5931033

Madhumangal Pal, Mrinmoy Hota, Tapan Kumar Pal

Publication date: 26 June 2001

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1023/a:1008791627588

zbMATH Keywords

combinatorial problemsanalysis of algorithmsdesign of algorithmsdirected acyclic graphindependent setmaximum weight \(k\)-independent set problemnetwork flow problempathsequential algorithmtrapezoid graphweighted trapezoid graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35)

Related Items (9)

Maximum weight independent set of circular-arc graph and its application ⋮ Selection of programme slots of television channels for giving advertisement: a graph theoretic approach ⋮ Efficient algorithm for the vertex connectivity of trapezoid graphs ⋮ On inertia and ratio type bounds for the \(k\)-independence number of a graph and their relationship ⋮ Spectral bounds for the \(k\)-independence number of a graph ⋮ Independent sets in graphs ⋮ Scheduling algorithm to select optimal programme slots in television channels: a graph theoretic approach ⋮ An efficient PRAM algorithm for maximum-weight independent set on permutation graphs ⋮ Algorithms and complexity of \(s\)-club cluster vertex deletion

This page was built for publication: An efficient algorithm for finding a maximum weight \(k\)-independent set of trapezoid graphs