Research Institute for Discrete Mathematics
Winter term 2016/2017
Tuesdays, from 16:00 to 17:30 in the Seminarraum, Research Institute for Discrete Mathematics.
Programming Task 1:
The description of the task is at the end of Set 3 above. Here you will find some useful material (which will be updated once in a while).
- Removed a few graph instances (named "myciel...") from the collection above. These were weighted instances with some lines starting with 'n', which your program is not required to
know how to handle.
- Fixed the number of edges in the instance "USA-road-d.USA.dmx". Somebody must have modified this file by hand (deleted lots of edges) and did not change the number of edges given in the
- Added collection of matching instances! For each graph instance "<graph_name>.dmx" you will find a matching instance "<graph_name>_matching_maximal.dmx" which I created using a
greedy algorithm that traverses the graph and extends the initial (empty) matching until it becomes maximal.
- Uploaded list of optimum values for our instances.
Tutor: Tomás Silveira Salles