The parallel complexity of approximating the high degree subgraph problem
type: Item
instance of: scholarly article
title: The parallel complexity of approximating the high degree subgraph problem
zbMATH Open document ID: 0913.68095
DOI: 10.1016/S0304-3975(97)00276-4
published in: Theoretical Computer Science
publication date: 1999-01-12T00:00:00Z
Mathematics Subject Classification ID: 68W15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1238809
zbMATH Keywords: P-completeness
zbMATH Keywords: parallel approximation algorithms
zbMATH Keywords: random graphs
author: Alexander E. Andreev
author: Andrea Clementi
author: Pilu Crescenzi
author: Elias Dahlhaus
author: Sergio De Agostino
MaRDI profile type: Publication
cites work: Q4004078
cites work: Q3682518
cites work: Q4895237
cites work: On the structure of linear graphs
cites work: Ordered vertex removal and subgraph problems
cites work: A model classifying algorithms as inherently sequential with applications to graph searching
cites work: Q4843270
cites work: Q4385522
cites work: Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
cites work: Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
cites work: Q5592127
full work available at URL: s0304-3975(97)00276-4
OpenAlex ID: W2002202793
description: scientific article; zbMATH DE number 1238809