Hamiltonian circuits in interval graph generalizations
type: Item
instance of: scholarly article
title: Hamiltonian circuits in interval graph generalizations
zbMATH Open document ID: 0627.68056
DOI: 10.1016/0020-0190(86)90135-3
author: Alan A. Bertossi
author: Maurizio A. Bonuccelli
published in: Information Processing Letters
publication date: 1986-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4020493
zbMATH Keywords: Hamiltonian circuit
zbMATH Keywords: intersection graphs
zbMATH Keywords: NP-complete
zbMATH Keywords: undirected path graphs
zbMATH Keywords: chordal graphs
zbMATH Keywords: double interval graphs
zbMATH Keywords: rectangle graphs
MaRDI profile type: Publication
full work available at URL: 0020-0190(86)90135-3
OpenAlex ID: W2028363955
cites work: Q3941433
cites work: The edge Hamiltonian path problem is NP-complete
cites work: Finding Hamiltonian circuits in proper interval graphs
cites work: Q4198056
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: A recognition algorithm for the intersection graphs of directed paths in directed trees
cites work: A recognition algorithm for the intersection graphs of paths in trees
cites work: Q3328583
cites work: The Hamiltonian Circuit Problem is Polynomial for 4-Connected Planar Graphs
cites work: Extremal Values of the Interval Number of a Graph
cites work: Hamilton Paths in Grid Graphs
cites work: The NP-completeness column: An ongoing guide
cites work: Finding Hamiltonian circuits in interval graphs
cites work: Q5588433
cites work: On double and multiple interval graphs
cites work: Characterizing circular-arc graphs
Recommended article: Finding Hamiltonian circuits in interval graphs
Recommended article: Q5202208
Recommended article: HAMILTONian circuits in chordal bipartite graphs
Recommended article: Hamiltonian circuits and paths in subset graphs with circular adjacency
Recommended article: Q5492585
Recommended article: Hamiltonian decomposition of generalized recursive circulant graphs
Recommended article: Hamiltonian properties on a class of circulant interconnection networks
Recommended article: Cycle Extendability of Hamiltonian Interval Graphs
Recommended article: Hamilton cycles in circuit graphs of matroids
Recommended article: Hamiltonian decomposition of recursive circulant graphs
description: scientific article; zbMATH DE number 4020493