On a Polynomially Solvable Subclass of the Clique Problem with Applications in Energy-Efficient Timetabling

Patrick Gemander ()
Additional contact information
Patrick Gemander: FAU Erlangen-Nürnberg

A chapter in Operations Research Proceedings 2018, 2019, pp 3-9 from Springer

Abstract: Abstract The clique problem under multiple-choice constraints is an N P $${\mathcal {N}\mathcal {P}}$$ -hard variant of the general clique problem, which incorporates a structure commonly found in real-world applications like underground, railway or runway scheduling. It is relevant whenever there is a set of decisions with discrete options for each decision and possible conflicts between options. In this article, we identify a polynomial-time solvable subclass and determine its complete convex hull using graph-theoretic arguments related to perfect graphs. Since the convex hull can have exponentially many facets, we present criteria on how to more efficiently find the stable sets required to describe the convex hull as well as a polynomial-time separation algorithm. Finally, the theoretical results were successfully applied to energy-efficient underground and railway scheduling.

Keywords: Clique problem; Perfect graphs; Convex hull; Scheduling (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:oprchp:978-3-030-18500-8_1

Ordering information: This item can be ordered from
http://www.springer.com/9783030185008

DOI: 10.1007/978-3-030-18500-8_1

Access Statistics for this chapter

More chapters in Operations Research Proceedings from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().