The parallel complexity of approximating the High Degree Subgraph problem
From MaRDI portal
Random graphs (graph-theoretic aspects) (05C80) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10) Parallel algorithms in computer science (68W10) Approximation algorithms (68W25)
Recommendations
- The parallel complexity of approximating the high degree subgraph problem
- Using maximal independent sets to solve problems in parallel
- scientific article; zbMATH DE number 4087453
- 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
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 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
(3)
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 Q6487954)
