Random Structures & Algorithms

Paper

01 Jan 1995

On the independence number of sparse graphs

View publication

Abstract

Let G be a regular graph of degree d on n points which contains no Kr (r ≥ 4). Let α be the independence number of G. Then we show for large d that α ≥ c(r)n . © 1995 John Wiley & Sons, Inc. Copyright © 1995 Wiley Periodicals, Inc., A Wiley Company

Related

Conference paper

Strategies for registering range images from unknown camera positions

Fausto Bernardini, Holly Rushmeier

Proceedings of SPIE - The International Society for Optical Engineering

Conference paper

Channel coding considerations for wireless LANs

Daniel J. Costello Jr., Pierre R. Chevillat, et al.

ISIT 1997

Paper

A globally convergent lagrangian barrier algorithm for optimization with general inequality constraints and simple bounds

A.R. Conn, Nick Gould, et al.

Mathematics of Computation

Paper

Quantum Simulators: Architectures and Opportunities

Ehud Altman, Kenneth R. Brown, et al.

PRX Quantum

View all publications