The longest path problem is polynomial on cocomparability graphs
type: Item
instance of: scholarly article
title: The longest path problem is polynomial on cocomparability graphs
zbMATH Open document ID: 1259.68094
author: Kyriaki Ioannidou
author: Stavros D. Nikolopoulos
published in: Algorithmica
publication date: 2013-03-05T00:00:00Z
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C45
Mathematics Subject Classification ID: 05C85
zbMATH DE Number: 6141206
zbMATH Keywords: longest path problem
zbMATH Keywords: cocomparability graphs
zbMATH Keywords: permutation graphs
zbMATH Keywords: polynomial algorithm
zbMATH Keywords: complexity
MaRDI profile type: Publication
full work available at URL: s00453-011-9583-5
OpenAlex ID: W2106934213
Wikidata QID: Q56639277
cites work: Linear algorithm for optimal path cover problem on interval graphs
cites work: The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
cites work: Finding Hamiltonian circuits in proper interval graphs
cites work: Graph Classes: A Survey
cites work: On computing a longest path in a tree
cites work: The Hamiltonian circuit problem for circle graphs is NP-complete
cites work: Paths in interval graphs and circular arc graphs
cites work: Finding Hamiltonian paths in cocomparability graphs using the bump number algorithm
cites work: Q4256006
cites work: Polynomial Algorithms for Hamiltonian Cycle in Cocomparability Graphs
cites work: Finding large cycles in Hamiltonian graphs
cites work: Finding Paths and Cycles of Superpolylogarithmic Length
cites work: Finding Long Paths, Cycles and Circuits
cites work: Q4198056
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Algorithmic graph theory and perfect graphs
cites work: Computing the bump number is easy
cites work: The longest path problem has a polynomial solution on interval graphs
cites work: Hamilton Paths in Grid Graphs
cites work: On approximating the longest path in a graph
cites work: Topics in Intersection Graph Theory
cites work: HAMILTONian circuits in chordal bipartite graphs
cites work: A note on the Hamiltonian circuit problem on directed path graphs
cites work: Simple Geometrical Intersection Graphs
cites work: Algorithms and Computation
cites work: Linear structure of bipartite permutation graphs and the longest path problem
cites work: Q4952685
cites work: Algorithms for long paths in graphs
DOI: 10.1007/S00453-011-9583-5
description: scientific article; zbMATH DE number 6141206