The Algorithm Design Manual Second Edition

Related Problems

: Constrained optimization (see page

407

), traveling salesman

problem (see page

533

).

---

15

Graph Problems: Polynomial-Time

Algorithmic graph problems constitute approximately one third of the problems

in this catalog. Problems from other sections could have been formulated equally

well in terms of graphs, such as bandwidth minimization and finite-state automata

optimization. Identifying the name of a graph-theoretic invariant or problem is one

of the primary skills of a good algorist. Indeed, the catalog will tell you exactly

how to proceed as soon as you figure out your particular problem’s name.

In this section, we deal only with problems for which there are efficient al-

gorithms to solve them. As there is often more than one way to model a given

application, it makes sense to look here before proceeding on to the harder formu-

lations.

The algorithms presented here have running times that grow polynomially with

the size of the graph. We adopt throughout the convention that n refers to the

number of vertices in a graph, while m is the number of edges.

Graphs are often best understood as drawings. Many interesting graph proper-

ties follow from the nature of a particular type of drawing, such as planar graphs.

Thus, we also discuss algorithms for drawing graphs, trees, and planar graphs.

Most advanced graph algorithms are difficult to program. However, good im-

plementations are available if you know where to look. The best general sources

include LEDA [

MN99]

and the Boost Graph Library [

SLL02]

. However, better

special-purpose codes exist for many problems.

See the Handbook of Graph Algorithms [

TNX08]

for up-to-date surveys on all

areas of graph algorithms. Other excellent surveys include van Leeuwen [

vL90a]

,

and several chapters in Atallah [

Ata98]

. Books specializing in graph algorithms

include:

• Sedgewick [

Sed98]

– The graph algorithms volume of this algorithms text

provides a comprehensive but gentle introduction to the field.

S.S. Skiena, The Algorithm Design Manual, 2nd ed., DOI: 10.1007/978-1-84800-070-4 15,

c

 Springer-Verlag London Limited 2008

---

476

1 5 .

G R A P H P R O B L E M S : P O L Y N O M I A L - T I M E

• Ahuja, Magnanti, and Orlin

[AMO93]

– While purporting to be a book on

network flows, it covers the gamut of graph algorithms with an emphasis on

operations research. Strongly recommended.

• Gibbons

[Gib85]

– A good book on graph algorithms, including planarity test-

ing, matching, and Eulerian/Hamiltonian cycles, as well as more elementary

topics.

• Even

[Eve79a]

– An older but still respected advanced text on graph al-

gorithms, with a particularly thorough treatment of planarity-testing algo-

rithms.

---

1 5 . 1

C O N N E C T E D C O M P O N E N T S

477

1

2

3

4

5

 

6

 

7

8

9

10

 11

12

13

1

2

3

4

8

9

10

 11

 

6

 

7

5

13

12

INPUT

OUTPUT