Finding Critical Independent Sets and Critical Vertex Subsets are Polynomial Problems

Abstract

It has been proved by mathematicians that finding a maximum independent set in some certain kinds of graphs is solvable in polynomial time (for example, line graphs, bipartite graphs, circle graphs, circular arc graphs and claw free graphs. But it is well-known that it is an NP-complete problem for general graphs. In this paper, we will investigate another problem -- finding a certain kind of independent sets in general graphs. It will be proved in this paper that finding a critical independent set of a graph is solvable in polynomial time.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Oct 15, 1989
Accession Number
ADA216547

Entities

People

  • Cun-quan Zhang

Organizations

  • West Virginia University

Tags

DTIC Thesaurus Topics

  • Abstracts
  • Air Force
  • Availability
  • Classification
  • Coverings
  • Inequalities
  • Mathematics
  • Monitoring
  • Polynomials
  • Scientific Research
  • Security
  • Universities
  • Virginia
  • West Virginia

Fields of Study

  • Mathematics

Readers

  • Approximation Theory.
  • Operations Research
  • Theoretical Analysis.