论文主要研究了两个主题，第二章和第三章中的树分解;第四章和第五章的路由问题。粗略地讲，一个图的树分解将图中每个顶点都映射到一个树的某个子树上并且满足每两个相邻的顶点所映射到的子树是相交的，即树上的每个顶点对应于图中的一个顶点子集，通常称为树分解的一个包。　　第二章主要研究最小树树分解，即宽度一定的树分解中包数最小的树分解。给定一个整数k≥5，证明了在树宽至多是k-1的连通图类中，找一个宽度至多是k的最小树树分解是NP-难的;特别地，当k=4时，该问题在树宽至多为3的平面图类中也是NP-难的。对于k≤3，我们设计了多项式时间算法，在一些特殊图类中，可以找到树宽至多是k的最小树树分解。这个研究成果已经被国际会议LAGOS2015接收发表。　　在第三章中，当研究k-弦图，即不包含长度大于k的生成圈的图，上的警察抓盗贼游戏时，受到了启发，发现了一类特殊的树分解，k-超毛毛虫树分解，其中每个包里都包含着一个小于k的支配集且该支配集中的顶点生成图中的一条路。给定一个图G和一个整数k≥3，设计了一个多项式时间算法，或者找到图G的一个长度大于k的生成圈;或者找到图G的一个k-超毛毛虫树分解。更进一步，研究了平面k-超毛毛虫的弦性。部分研究成果已经发表在国际会议ICALP2012的论文集中和期刊Algorithmica中。　　第四章研究紧凑路由算法。作为k-超毛毛虫树分解的一个应用，设计了一个有k-超毛毛虫树分解的图类的紧凑路由算法，其每个顶点的路由表存储量至多是O（klogΔ+logn），而且其算法增量至多是O(klogΔ)，即对于图中任意两个顶点，我们的算法所找到的他们之间的路的长度至多是他们之间的最短路的长度加上O(k logΔ)。　　最后，第五章研究了奖励收集斯坦纳树问题。在树宽至多是2的图类里，设计了该问题的线性时间算法。更进一步，研究了不确定性奖励收集斯坦纳树问题，具体来说是带有区间数据的奖励收集斯坦纳树问题。提出了两个风险模型，Min-Max Risk模型和Min-Sum Risk模型。而且在树宽至多是2的图类里，分别设计了两个模型下的多项式时间算法。最后还对这两个模型的算法做了仿真实验，比较他们在实际应用中的优劣。这些研究成果已经发表在国际会议AAIM2010的会议论文集和期刊Acta MathematicaeApplicatae Sinica中。