Ordered vertex removal and subgraph problems

DOI10.1016/0022-0000(89)90026-3MaRDI QIDQ582090zbMATH OpenOpenAlexFDO

Authors Raymond Greenlaw

Publication date 1989

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(89)90026-3

zbMATH Keywords

complexity theorycomputational complexityHigh Degree Vertex Removal ProblemLow Degree Subgraph ProblemLow Degree Vertex Removal ProblemNP-complete

Mathematics Subject Classification ID

Complexity of computation (including implicit computational complexity) (03D15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Node-and edge-deletion NP-complete problems
• scientific article; zbMATH DE number 30298
• scientific article; zbMATH DE number 4060745
• The lexicographically first maximal subgraph problems:P-completeness andNC algorithms
• scientific article; zbMATH DE number 4047154

Cites work

• A taxonomy of problems with fast parallel algorithms
• scientific article; zbMATH DE number 3555903 (Why is no real title available?)
• scientific article; zbMATH DE number 3558962 (Why is no real title available?)
• scientific article; zbMATH DE number 3560737 (Why is no real title available?)
• scientific article; zbMATH DE number 3566230 (Why is no real title available?)
• scientific article; zbMATH DE number 3571502 (Why is no real title available?)
• On uniform circuit complexity
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes

Cited in

(6)

• The parallel complexity of approximating the high degree subgraph problem
• Constructing the highest degree subgraph for dense graphs is in \({\mathcal N}{\mathcal C}{\mathcal A}{\mathcal S}\)
• On parallelizing a greedy heuristic for finding small dominant sets
• scientific article; zbMATH DE number 30298 (Why is no real title available?)
• The parallel complexity of approximation algorithms for the maximum acyclic subgraph problem
• The parallel complexity of approximating the High Degree Subgraph problem

This page was built for publication: Ordered vertex removal and subgraph problems

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