What are the least tractable instances of max independent set?

David S. Johnson, Mario Szegedy

Research output: Contribution to conferencePaper

19 Scopus citations

Abstract

For this note we say that a problem is computable in time sub-exponential in n if there is an effectively computable monotone increasing function g(n) with lim n→∞ g(n) = ∞ such that the problem is computable in time O(2 n/g(n)). We establish that a maximal independent set of a graph on n vertices can be found in time sub-exponential in n if the same holds for the class of those graphs that have maximum degree at most 3.

Original languageEnglish (US)
StatePublished - Jan 1 1999
Externally publishedYes
EventProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA
Duration: Jan 17 1999Jan 19 1999

Other

OtherProceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms
CityBaltimore, MD, USA
Period1/17/991/19/99

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Fingerprint Dive into the research topics of 'What are the least tractable instances of max independent set?'. Together they form a unique fingerprint.

Cite this