Repository logo

Browsing by Subject "np-completeness"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • thumbnail.journal.alt
    Item type:Article, Access status: Open Access ,
    Szeregowanie rozrzedzonych systemów zadań jednostkowych 1- i 2-procesowych w oknach czasowych
    (Wydawnictwa AGH, 2005) Giaro, Krzysztof; Kubale, Marek
    In the paper sparse systems of dedicated 1- and 2-processor tasks with unit execution times are considered. Polynomial-time algorithms based on dynamic programming are given. These algorithms allow finding optimal solutions with respect to broad range of criterion functions. The sparsity of a system is measured in terms of the number of edges in the corresponding scheduling graph. More precisely, we are focused on graphs whose cyclomatic number is bounded by a constant. Our algorithms invoke procedures for finding maximal matching in graphs.