Efficient parallel recognition of some circular arc graphs. I
type: Item
instance of: scholarly article
title: Efficient parallel recognition of some circular arc graphs. I
zbMATH Open document ID: 0768.68127
DOI: 10.1007/BF01190897
author: Lin Chen
published in: Algorithmica
publication date: 1993-05-16T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68W15
zbMATH DE Number: 168416
zbMATH Keywords: claw-free graphs
zbMATH Keywords: parallel algorithms
zbMATH Keywords: circular arc graphs
zbMATH Keywords: interval graphs
zbMATH Keywords: PRAM
MaRDI profile type: Publication
cites work: Finding maximum cliques on circular-arc graphs
cites work: An optimal parallel algorithm for the minimum circle-cover problem
cites work: Finding Hamiltonian circuits in proper interval graphs
cites work: Some parallel algorithms on interval graphs
cites work: Dominating sets and domatic number of circular arc graphs
cites work: Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
cites work: A parallel circle-cover minimization algorithm
cites work: Q4028894
cites work: Parallel recognition of the consecutive ones property with applications
cites work: Parallel Merge Sort
cites work: Faster optimal parallel prefix sums and list ranking
cites work: Relations between Concurrent-Write Models of Parallel Computation
cites work: Incidence matrices and interval graphs
cites work: The Complexity of Coloring Circular Arcs and Chords
cites work: Algorithms on circular-arc graphs
cites work: Q3328583
cites work: Stability in circular arc graphs
cites work: Efficient algorithms for interval graphs and circular-arc graphs
cites work: Parallel recognition and decomposition of two terminal series parallel graphs
cites work: Maximum Weight Clique Algorithms for Circular-Arc Graphs and Circle Graphs
cites work: SOME APPLICATIONS OF GRAPH THEORY AND RELATED NON‐METRIC TECHNIQUES TO PROBLEMS OF APPROXIMATE SERIATION: THE CASE OF SYMMETRIC PROXIMITY MEASURES
cites work: The NP-completeness column: an ongoing guide
cites work: Parallel Prefix Computation
cites work: On a circle-cover minimization problem
cites work: Minimum Cuts for Circular-Arc Graphs
cites work: A Linear Time Algorithm for Deciding Interval Graph Isomorphism
cites work: An Optimal Algorithm for Finding a Maximum Independent Set of a Circular-Arc Graph
cites work: An $O(n^2 )$ Algorithm for Coloring Proper Circular Arc Graphs
cites work: Q5588432
cites work: An optimal parallel circle-cover algorithm
cites work: An 0(n log n\(+m\,\log \,\log \,n)\) maximum weight clique algorithm for circular-arc graphs
cites work: Finding the maximum, merging, and sorting in a parallel computation model
cites work: Characterization problems for graphs, partially ordered sets, lattices, and families of sets
cites work: Matrix characterizations of circular-arc graphs
cites work: Structure theorems for some circular-arc graphs
cites work: Coloring a Family of Circular Arcs
cites work: An Efficient Test for Circular-Arc Graphs
full work available at URL: https://doi.org/10.1007/bf01190897
OpenAlex ID: W4251188792
description: scientific article; zbMATH DE number 168416