The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
type: Item
instance of: scholarly article
title: The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
zbMATH Open document ID: 1200.05212
author: Katerina Asdre
author: Stavros D. Nikolopoulos
published in: Algorithmica
publication date: 2010-09-27T00:00:00Z
full work available at URL: http://citeseerx.ist.psu.edu/viewdoc/summary
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 5791714
zbMATH Keywords: Perfect graphs
zbMATH Keywords: Interval graphs
zbMATH Keywords: Path cover
zbMATH Keywords: Fixed-endpoint path cover
zbMATH Keywords: Linear-time algorithms
MaRDI profile type: Publication
OpenAlex ID: W2023957019
cites work: Linear algorithm for optimal path cover problem on interval graphs
cites work: A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
cites work: Finding Hamiltonian circuits in proper interval graphs
cites work: Hamiltonian circuits in interval graph generalizations
cites work: Graph Classes: A Survey
cites work: Paths in interval graphs and circular arc graphs
cites work: The directed subgraph homeomorphism problem
cites work: Q4198056
cites work: The Planar Hamiltonian Circuit Problem is NP-Complete
cites work: Q3328583
cites work: An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
cites work: The Hamiltonian problem on distance-hereditary graphs
cites work: Linear-time algorithms for the Hamiltonian problems on distance-hereditary graphs
cites work: Solving the path cover problem on circular-arc graphs by using an approximation algorithm
cites work: On the Computational Complexity of Combinatorial Problems
cites work: Finding Hamiltonian circuits in interval graphs
cites work: An optimal path cover algorithm for cographs
cites work: HAMILTONian circuits in chordal bipartite graphs
cites work: A time-optimal solution for the path cover problem on cographs.
cites work: Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
cites work: Computing and Combinatorics
cites work: A unified approach to domination problems on interval graphs
cites work: Graph minors. XIII: The disjoint paths problem
cites work: Disjoint paths in graphs
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: Optimal path cover problem on block graphs and bipartite permutation graphs
cites work: 2-linked graphs
cites work: ON COMPUTING LONGEST PATHS IN SMALL GRAPH CLASSES
DOI: 10.1007/S00453-009-9292-5
Recommended article: A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
Recommended article: A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
Recommended article: An optimal algorithm for the \(k\)-fixed-endpoint path cover on proper interval graphs
Recommended article: Q3104272
Recommended article: The Longest Path Problem Is Polynomial on Interval Graphs
Recommended article: The longest path problem has a polynomial solution on interval graphs
Recommended article: Polynomial Fixed-parameter Algorithms: A Case Study for Longest Path on Interval Graphs
Recommended article: Polynomial fixed-parameter algorithms: a case study for longest path on interval graphs
Recommended article: A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
Recommended article: The 2-Terminal-Set Path Cover Problem and Its Polynomial Solution on Cographs
description: scientific article; zbMATH DE number 5791714