We propose a dynamic programming procedure for computing the clique of maximum weight on a class of graphs arising in the solution of train timetabling problems. These graphs generalize, in two ways permutation graphs, defined as the intersection graphs of segments joining two parallel lines. First, two segments are joined by an edge not only if they intersect but also if their endpoints are sufficiently close. Second, two parallel segments may be joined by an edge even if they are arbitrarily far away from each other.

Finding Cliques of Maximum Weight on a Generalization of Permutation Graphs

CACCHIANI, VALENTINA;CAPRARA, ALBERTO;TOTH, PAOLO
2013

Abstract

We propose a dynamic programming procedure for computing the clique of maximum weight on a class of graphs arising in the solution of train timetabling problems. These graphs generalize, in two ways permutation graphs, defined as the intersection graphs of segments joining two parallel lines. First, two segments are joined by an edge not only if they intersect but also if their endpoints are sufficiently close. Second, two parallel segments may be joined by an edge even if they are arbitrarily far away from each other.
V. Cacchiani; A. Caprara; P. Toth
File in questo prodotto:
Eventuali allegati, non sono esposti

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11585/113185
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact