Sumários

T11

16 Maio 2017, 13:00 • Isabel Gama Nunes

Polynomial time reductions (packing and covering problems).

Reductions via "gadgets": the satisfiability problem (constraint satisfaction problems).

Efficient certification and the definition of NP.

P10

9 Maio 2017, 15:00 • Isabel Gama Nunes

Resolution of exercises 6, 7.

T10

9 Maio 2017, 13:00 • Isabel Gama Nunes

Network flow.

A first application: The bipartite matching problem.

Disjoint paths in directed and undirected graphs.

Extensions to the maximum­ flow problem: Circulation with demands; circulations with demands and lower bounds.

P9

2 Maio 2017, 15:00 • Isabel Gama Nunes

Resolution of exercises 1, 2.

T9

2 Maio 2017, 13:00 • Isabel Gama Nunes

Network flow.

The maximum­ flow problem and the Ford­Fulkerson algorithm.

Maximum flows and minimum cuts in a flow network.

Choosing good augmenting paths.