Efficient reduction for path problems on circular-arc graphs
type: Item
instance of: scholarly article
title: Efficient reduction for path problems on circular-arc graphs
zbMATH Open document ID: 0726.68059
DOI: 10.1007/BF01931279
author: S. R. Arikati
author: C. Pandu Rangan
author: Glenn K. Manacher
published in: BIT
publication date: 1991-01-01T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 4199649
zbMATH Keywords: interval graphs
zbMATH Keywords: parity path problem
zbMATH Keywords: two path problem
MaRDI profile type: Publication
cites work: A linear algorithm for the group path problem on chordal graphs
cites work: Corrigendum to: On the complexity of testing for odd holes and induced odd paths
cites work: Dominating sets and domatic number of circular arc graphs
cites work: Q3328583
cites work: Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
cites work: Finding Hamiltonian circuits in interval graphs
cites work: Q4732130
cites work: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
cites work: A Polynomial Solution to the Undirected Two Paths Problem
cites work: An Efficient Test for Circular-Arc Graphs
Recommended article: Solving the path cover problem on circular-arc graphs by using an approximation algorithm
Recommended article: On the approximability of path and cycle problems in arc-dependent networks
Recommended article: Q4028893
Recommended article: Linear time algorithms on circular-arc graphs
Recommended article: Computing and counting longest paths on circular-arc graphs in polynomial time
Recommended article: Efficient and perfect domination on circular-arc graphs
Recommended article: An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
Recommended article: Efficient Algorithms for the Domination Problems on Interval and Circular-Arc Graphs
Recommended article: Q3361906
description: scientific article; zbMATH DE number 4199649