An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
type: Item
instance of: scholarly article
title: An optimal algorithm for shortest paths on weighted interval and circular-arc graphs, with applications
zbMATH Open document ID: 0830.68051
DOI: 10.1007/BF01192049
author: Mikhail J. Atallah
author: Danny Z. Chen
author: Der-Tsai Lee
published in: Algorithmica
publication date: 1996-02-04T00:00:00Z
Mathematics Subject Classification ID: 68W10
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 809153
zbMATH Keywords: shortest paths
zbMATH Keywords: interval graphs
zbMATH Keywords: circular-arc graph
zbMATH Keywords: circle-cover problem
MaRDI profile type: Publication
cites work: Q4091421
cites work: An optimal parallel algorithm for the minimum circle-cover problem
cites work: Parallel circle-cover algorithms
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A linear-time algorithm for a special case of disjoint set union
cites work: Q3328583
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: On a circle-cover minimization problem
cites work: An optimal algorithm to solve the all-pair shortest path problem on interval graphs
cites work: RESTRICTED TRACK ASSIGNMENT WITH APPLICATIONS
cites work: A class of algorithms which require nonlinear time to maintain disjoint sets
cites work: Preserving order in a forest in less than logarithmic time and linear space
full work available at URL: https://doi.org/10.1007/bf01192049
OpenAlex ID: W2763025185
description: scientific article; zbMATH DE number 809153