What are the least tractable instances of max independent set?

David S. Johnson, Mario Szegedy

Research output: Contribution to conferencePaper

19 Citations (Scopus)

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

Fingerprint

Independent Set
Maximal Independent Set
Monotone Function
Increasing Functions
Graph in graph theory
Maximum Degree

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Cite this

Johnson, D. S., & Szegedy, M. (1999). What are the least tractable instances of max independent set?. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .
Johnson, David S. ; Szegedy, Mario. / What are the least tractable instances of max independent set?. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .
@conference{33c38c5014d34d618fc21ffe682ccdc8,
title = "What are the least tractable instances of max independent set?",
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.",
author = "Johnson, {David S.} and Mario Szegedy",
year = "1999",
month = "1",
day = "1",
language = "English (US)",
note = "Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms ; Conference date: 17-01-1999 Through 19-01-1999",

}

Johnson, DS & Szegedy, M 1999, 'What are the least tractable instances of max independent set?' Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, 1/17/99 - 1/19/99, .

What are the least tractable instances of max independent set? / Johnson, David S.; Szegedy, Mario.

1999. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .

Research output: Contribution to conferencePaper

TY - CONF

T1 - What are the least tractable instances of max independent set?

AU - Johnson, David S.

AU - Szegedy, Mario

PY - 1999/1/1

Y1 - 1999/1/1

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0032776990&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0032776990&partnerID=8YFLogxK

M3 - Paper

ER -

Johnson DS, Szegedy M. What are the least tractable instances of max independent set?. 1999. Paper presented at Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms, Baltimore, MD, USA, .