The parallel complexity of approximating the high degree subgraph problem

DOI10.1016/S0304-3975(97)00276-4MaRDI QIDQ1275085zbMATH OpenOpenAlexFDO

Authors Alexander E. Andreev, Andrea Clementi, Pilu Crescenzi, Elias Dahlhaus, Sergio De Agostino

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

P-completenessparallel approximation algorithmsrandom graphs

Mathematics Subject Classification ID

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

Recommendations

• The parallel complexity of approximating the High Degree Subgraph problem
• scientific article; zbMATH DE number 4087453
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)
• Parallel Complexity of the Connected Subgraph Problem

Cites work

• 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
• scientific article; zbMATH DE number 3904630 (Why is no real title available?)
• scientific article; zbMATH DE number 53883 (Why is no real title available?)
• scientific article; zbMATH DE number 1142306 (Why is no real title available?)
• scientific article; zbMATH DE number 784042 (Why is no real title available?)
• scientific article; zbMATH DE number 934538 (Why is no real title available?)
• scientific article; zbMATH DE number 3311627 (Why is no real title available?)
• On the structure of linear graphs
• Ordered vertex removal and subgraph problems
• Short vertex disjoint paths and multiconnectivity in random graphs: Reliable network computing

Cited in

(5)

• Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• Parallel Complexity of the Connected Subgraph Problem
• scientific article; zbMATH DE number 562727 (Why is no real title available?)
• The parallel complexity of approximating the High Degree Subgraph problem

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1275085)