HAMILTONIAN CIRCUITS IN INTERVAL GRAPH GENERALIZATIONS

被引：50

作者：

BERTOSSI, AA

BONUCCELLI, MA

机构：

[1] Univ di Pisa, Pisa, Italy, Univ di Pisa, Pisa, Italy

来源：

INFORMATION PROCESSING LETTERS | 1986年 / 23卷 / 04期

关键词：

COMPUTER PROGRAMMING - Algorithms;

D O I：

10.1016/0020-0190(86)90135-3

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We consider the problem of finding a Hamiltonian circuit in some classes of intersection graphs which generalize interval graphs. We show that the problem is NP-complete for undirected path graphs (and hence chordal graphs), double interval graphs, and rectangle graphs.

引用

页码：195 / 200

页数：6

共 18 条

[1]

Berge C., 1973, GRAPHS HYPERGRAPHS, V7

[2] FINDING HAMILTONIAN CIRCUITS IN PROPER INTERVAL-GRAPHS [J].