Об оптимизационных проблемах включения треков - Шахбазян, К.В.; Шукурян, Ю.Г. (Кибернетика и системный анализ, 2010)
Показано поліноміальну складність оптимізаційних проблем для кінцевої множини треків Т: 1) знайти трек найбільшої довжини, вкладений в кожен трек з множини Т; 2) знайти найкоротший трек, не вкладений в кожен трек з множини Т; 3) знайти найкоротший трек, в який вкладено кожен трек з множини Т; 4) знайти трек найбільшої довжини, в який не вкладено кожен трек з множини T. Four optimization problems for a finit set of traces are considered: (i) find the longest trace that is included in each trace from a given finite set T of traces, (ii) find the shortest trace that is not included in every trace from a given finite set T of traces, (iii) find the shortest trace that includes every trace from a given finite set T of traces, (iv) find the longest trace that does not include each trace from a given finite set T of traces.