On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
type: Item
instance of: scholarly article
title: On the complexity of hamiltonian path and cycle problems in certain classes of digraphs
zbMATH Open document ID: 0934.05082
DOI: 10.1016/S0166-218X(99)00064-5
published in: Discrete Applied Mathematics
publication date: 2000-04-09T00:00:00Z
review text: This is the most comprehensive and updated survey article with very detailed information and discussion about results on sequential and parallel complexity of hamiltonian problems for various classes of directed graphs that generalize tournaments (such as, locally in-semicomplete digraphs, semicomplete multipartite digraphs, path-mergeable digraphs, quasi-transitive digraphs, etc.). A few new results about hamiltonian path starting at a given vertex for some digraphs are also proved in this paper.
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05-02
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1340625
zbMATH Keywords: Hamilton path
zbMATH Keywords: Hamilton cycle
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: parallel algorithm
zbMATH Keywords: tournament locally in-semicomplete digraph
zbMATH Keywords: semicomplete multipartite digraph
zbMATH Keywords: path-mergeable digraph
zbMATH Keywords: quasi-transitive digraph
author: Jørgen Bang-Jensen
author: G. Gutin
MaRDI profile type: Publication
full work available at URL: s0166-218x(99)00064-5
OpenAlex ID: W1984883238
Wikidata QID: Q128066106
description: scientific article; zbMATH DE number 1340625