Change search
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf
Complexity of some special types of timetabling problems
École Polytechnique Fédérale de Lausanne.
Laboratoire d'Informatique d'Avignon.
2002 (English)In: Journal of Scheduling, ISSN 1094-6136, E-ISSN 1099-1425, Vol. 5, no 2, p. 171-183Article in journal (Refereed) Published
Abstract [en]

Starting from the simple class-teacher model of timetabling (where timetables correspond to edgecolorings of a bipartite multigraph), we consider an extension defined as follows: we assume that the set of classes is partitioned into groups. In addition to the teachers giving lectures to individual classes, we have a collection of teachers who give all their lectures to groups of classes. We show that when there is one such teacher giving lectures to three groups of classes, the problem is NP-complete. We also examine the case where there are at most two groups of classes and we give a polynomial procedure based on network flows to find a timetable using at most t periods.

Place, publisher, year, edition, pages
2002. Vol. 5, no 2, p. 171-183
National Category
Mathematical Analysis
Research subject
Mathematics
Identifiers
URN: urn:nbn:se:ltu:diva-14822DOI: 10.1002/jos.97Scopus ID: 2-s2.0-0346387208Local ID: e3f75040-ac87-11db-aeba-000ea68e967bOAI: oai:DiVA.org:ltu-14822DiVA, id: diva2:987795
Note

Validerad; 2002; 20070125 (kani)

Available from: 2016-09-29 Created: 2016-09-29 Last updated: 2018-07-10Bibliographically approved

Open Access in DiVA

No full text in DiVA

Other links

Publisher's full textScopus

Search in DiVA

By author/editor
Asratian, Armen S.
In the same journal
Journal of Scheduling
Mathematical Analysis

Search outside of DiVA

GoogleGoogle Scholar

doi
urn-nbn

Altmetric score

doi
urn-nbn
Total: 24 hits
CiteExportLink to record
Permanent link

Direct link
Cite
Citation style
  • apa
  • ieee
  • modern-language-association-8th-edition
  • vancouver
  • Other style
More styles
Language
  • de-DE
  • en-GB
  • en-US
  • fi-FI
  • nn-NO
  • nn-NB
  • sv-SE
  • Other locale
More languages
Output format
  • html
  • text
  • asciidoc
  • rtf