Treewidth: theory and applications to computer science
Ikusi/ Ireki
Data
2015-10-15Egilea
Matellanes Pastoriza, Ivan
Laburpena
This report is an introduction to the concept of treewidth, a property of graphs
that has important implications in algorithms. Some basic concepts of graph
theory are presented in the first chapter for those readers that are not familiar
with the notation. In Chapter 2, the definition of treewidth and some different
ways of characterizing it are explained. The last two chapters focus on the
algorithmic implications of treewidth, which are very relevant in Computer
Science. An algorithm to compute the treewidth of a graph is presented and
its result can be later applied to many other problems in graph theory, like
those introduced in the last chapter.