Ordered vertex removal and subgraph problems

DOI10.1016/0022-0000(89)90026-3zbMath0689.68053OpenAlexW2030970081MaRDI QIDQ582090

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

computational complexityNP-completecomplexity theoryHigh Degree Vertex Removal ProblemLow Degree Subgraph ProblemLow Degree Vertex Removal Problem

Mathematics Subject Classification ID

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

Related Items (4)

On parallelizing a greedy heuristic for finding small dominant sets ⋮ 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 ⋮ The parallel complexity of approximating the high degree subgraph problem

Cites Work

• On uniform circuit complexity
• A taxonomy of problems with fast parallel algorithms
• Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

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