The parallel complexity of approximating the high degree subgraph problem

DOI10.1016/S0304-3975(97)00276-4zbMath0913.68095OpenAlexW2002202793MaRDI QIDQ1275085

Sergio De Agostino, Alexander E. Andreev, Elias Dahlhaus, Pierluigi Crescenzi, Andrea E. F. Clementi

Publication date: 12 January 1999

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(97)00276-4

zbMATH Keywords

random graphsP-completenessparallel approximation algorithms

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Related Items (1)

Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)

Cites Work

• Ordered vertex removal and subgraph problems
• A model classifying algorithms as inherently sequential with applications to graph searching
• Hammock-on-ears decomposition: A technique for the efficient parallel solution of shortest paths and other problems
• On the structure of linear graphs
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: The parallel complexity of approximating the high degree subgraph problem