Paths and cycles in extended and decomposable digraphs
type: Item
instance of: scholarly article
title: Paths and cycles in extended and decomposable digraphs
zbMATH Open document ID: 0872.05028
DOI: 10.1016/S0012-365X(96)00038-6
published in: Discrete Mathematics
publication date: 1997-10-07T00:00:00Z
review text: An extended locally semicomplete digraph, or extended LSD for short, is a digraph that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. The paper characterizes Hamiltonian extended LSDs as well as extended LSDs containing Hamiltonian paths, implying polynomial algorithms for finding a longest path and a longest cycle in an extended LSD. It is shown that the longest path problem is polynomially solvable for totally \(\Phi_0\)-decomposable digraphs. Similar results are obtained for the longest cycle problem and other problems on cycles in subfamilies of totally \(\Phi_0\)-decomposable digraphs.
Mathematics Subject Classification ID: 05C38
Mathematics Subject Classification ID: 05C20
zbMATH DE Number: 1019049
zbMATH Keywords: digraph
zbMATH Keywords: Hamiltonian paths
zbMATH Keywords: longest path problem
zbMATH Keywords: longest cycle problem
author: Jørgen Bang-Jensen
author: G. Gutin
reviewed by: Wai-Kai Chen
MaRDI profile type: Publication
cites work: Locally semicomplete digraphs: A generalization of tournaments
cites work: On the structure of locally semicomplete digraphs
cites work: Vertex heaviest paths and cycles in quasi-transitive digraphs
cites work: Weakly Hamiltonian-connected ordinary multipartite tournaments
cites work: Quasi‐transitive digraphs
cites work: Q4039999
cites work: Q5422499
cites work: Connectivity properties of locally semicomplete digraphs
cites work: Finding a Longest Path in a Complete Multipartite Digraph
cites work: Q4325297
cites work: Characterization of vertex pancyclic and pancyclic ordinary complete multipartite digraphs
cites work: Hamilton Cycles in Oriented Graphs
cites work: Cycles and paths in bipartite tournaments with spanning configurations
full work available at URL: s0012-365x(96)00038-6
OpenAlex ID: W2080732695
description: scientific article; zbMATH DE number 1019049