Open Questions: Combinatorics, Graph Theory, and Computation
[Home] [Up]
[Glossary]
[Topic Index]
[Site Map]
See also: Quantum information and computing 
DNA and molecular computing
Introduction
Site indexes

Math Forum Internet Mathematics Library: Discrete Math
 Alphabetized list of links with extensive annotations.

Math Forum: Advanced Discrete Mathematics
 Selected list of links with extensive annotations.

Mathematics Archives  Combinatorics
 Extensive annotated list of links.

Mathematics Archives  Discrete Mathematics
 Extensive annotated list of links.

Open Directory Project: Combinatorics
 Categorized and annotated combinatorics links. A version of this
list is at
Google, with entries sorted in "page rank" order.

Galaxy: Combinatorics
 Categorized site directory. Entries usually include
descriptive annotations.
Has a subcategory for
graph theory.
Sites with general resources

The Electronic Journal of Combinatorics and The World
Combinatorics Exchange
 And online journal and Web site with resources for
combinatorial people.

Open Problems for Undergraduates
 About open problems in discrete mathematics  graph theory and
combinatorial geometry mostly. Although the problems are easily
stated, they may be quite hard. By Robert Hochberg, located at the
Center for Discrete Mathematics & Theoretical Computer Science
(DIMACS) site.

An Introduction to the Theory of Computation
 Material from a course at Ohio State University, by
Eitan M. Gurari. Includes information on NP and NPcomplete
problems.
Algorithms, computability, computational complexity

Computational complexity theory
 Article from
Wikipedia.
See also
Computation,
Computabililty theory,
Decision problem.

Wikibooks: Discrete Mathematics
 Textbook in the
Wikibooks collection. A work in progress, but already contains
much useful information.

Algorithmns and Complexity
 Complete first edition (1986) of a book by
Herbert S. Wilf,
in PDF format.

An Introduction to the Theory of Computation
 Complete 1989 book by Eitan M. Gurari (HTML/hypertext).
P, NP, and NPcomplete problems

The P versus NP Problem
 Brief description of the problem at the
Clay Mathematics Institute site by Stephen Cook.
(A more complete description is available as a PDF file.)

Complexity classes P and NP
 Article from
Wikipedia.

MillionDollar Minesweeper
 Wellwritten article for a general audience on the Minesweeper
game, by Ian Stewart. This is used to explain the P vs. NP problem.

CMU professor honored for computational complexity
breakthrough
 May 2007 news article about award of 2007 ACM Gödel Prize
to Steven Rudich and Alexander A. Razborov for their work on the
P vs. NP problem, in which they showed that the type of proof
technique known as "natural proofs" cannot solve the problem.

Heuristic Algorithms
 This is the text for a course given by Forbes Lewis. Several
introductory chapters deal with P, NP, and NPcomplete problems.
There is also material on neural networks, genetic algrorithms,
and DNA computing.

Data Structures and Algorithms: Hard or Intractable Problems
 Part of course material by John Morris. This page is on
the distinction between "easy" problems (class P) and harder
problems (NP). The problems of traversing a graph so that each
edge is crossed exactly once is compared with graph traversal
where each vertex is encountered exactly once. Other examples
of NP problems are given.

TSPBIB Home Page
 "A comprehensive listing of papers, source code, preprints,
technical reports, etc, available on the Internet about the
Traveling Salesman Problem (TSP) and some associated problems."
Compiled by
Pablo Moscato.

The Travelling Salesman Problem
 Nice tutorial page by
Robert Dakin
Graph theory

Graph theory
 Article from
Wikipedia.
See also
Graph (mathematics),
Glossary of graph theory.

Perfect Graphs
 An outline (literally) of some of the conjectures and open
problems related to perfect graphs. Part of the
Workshop Website Network of the
American Institute of Matheamtics.

Unsolved Problems in Graph Theory
 Mostly from the book Graph Theory with Applications,
by Bondy and Murty.

Problems in Topological Graph Theory
 Compiled by Dan Archdeacon.

Graph Theory
 Complete online book by Reinhard Diestel, in PDF format
(printing disabled).

Data Structures and Algorithms: Graph Algorithms
 Part of course material by John Morris. This page is on
minimal spanning trees. There's another page on
Dijkstra's algorithm for finding the shortest path between
points in a graph.

Journal of Graph Algorithms and Applications
 Free, refereed online journal.
Discrete mathematics, combinatorics

Combinatorics
 Article from
Wikipedia.
See also
List of combinatorics topics.

Open Problems in Discrete Math
 Collected by
Matt DeVos.

The Electronic Journal of Combinatorics: Dynamic Surveys
 Survey articles (in various formats) on contemporary2
research topics in combinatorics, periodically updated. The
journal's home page
has other useful information and external links.

Discrete Mathematics & Theoretical Computer Science
 Free, refereed online journal.
Computer theoremproving

The Coq proof assistant
 "The Coq tool is a formal proof management system: a proof
done with Coq is mechanically checked by the machine."
The site provides news and
general information about Coq, documentation, related tools,
as well as ability to download Coq.
 Minesweeper is NPcomplete
Richard Kaye
Mathematical Intelligencer, Spring 2000, pp. 915
 The article elucidates the concepts of NP and NPcomplete
problems through a proof that the game of Minesweeper is
NPcomplete.
 Descriptive Complexity: A Logician's Approach to Computation
N. Immerman
Notices of the AMS, October 1995, pp. 11271133
 As usually described, the complexity of a computation is
evaluated in terms of some specific computational model  some
sort of abstract computing device. However, the notion of
complexity can be described completely in terms of traditional
mathematical logic.
[Article in PDF format]
 David Harel  Computers Ltd.: What They Really Can't Do
Oxford University Press, 2000
 What computers really can't do is to solve NPcomplete
problems within the probable lifetime of the universe. This short
book by a distinguished computer scientist provides an elementary
explanation of this limitation. It also discusses something that
computers can do with very clever algorithms  cryptogrphy.
Home
Copyright © 200204 by Charles Daney, All Rights Reserved