Paper Info
Title
Ordered vertex removal and subgraph problems
Abstract
Several new graph theoretic problems, which arise naturally from existing coloring algorithms, are defined. The complementary High Degree Vertex Removal Problem and Low Degree Vertex Removal Problem are both shown to be NP-complete. The Low Degree Subgraph Problem is defined and shown to be NP-complete, whereas, the “complementary” problem for high degree subgraphs was previously shown to be P-complete. Since the obvious sequential algorithms for computing the low degree subgraph and high degree subgraph are based on high degree vertex removal and low degree vertex removal, respectively, we find this is an interesting result. The “greedy” versions of the vertex removal and subgraph are shown to be P-complete. In addition, a natural lexicographic version of the Low Degree Subgraph Problem is shown to be NP-complete.
Year
DOI
Venue
1989
10.1016/0022-0000(89)90026-3
Journal of Computer and System Sciences
Field
DocType
Volume
Discrete mathematics,Combinatorics,Vertex (geometry),Maximum common subgraph isomorphism problem,Vertex (graph theory),Induced subgraph isomorphism problem,Neighbourhood (graph theory),Degree (graph theory),Feedback vertex set,Subgraph isomorphism problem,Mathematics
Journal
39
Issue
ISSN
Citations 
3
0022-0000
4
PageRank 
References 
Authors
0.61
6
1
Name
Order
Citations
PageRank
Raymond Greenlaw114218.56