### 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 language | English (US) |
---|---|

State | Published - Jan 1 1999 |

Externally published | Yes |

Event | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms - Baltimore, MD, USA Duration: Jan 17 1999 → Jan 19 1999 |

### Other

Other | Proceedings of the 1999 10th Annual ACM-SIAM Symposium on Discrete Algorithms |
---|---|

City | Baltimore, MD, USA |

Period | 1/17/99 → 1/19/99 |

### Fingerprint

### All Science Journal Classification (ASJC) codes

- Software
- Mathematics(all)

### Cite this

*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, .

}

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

Research output: Contribution to conference › Paper

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 -