Dissertation > Excellent graduate degree dissertation topics show

The Algorithms for the Minimum Edge Ranking Problem

Author: WanMaoWu
Tutor: WangJianXin
School: Central South University
Course: Computer Science and Technology
Keywords: Minimum edge ranking Minimum vertex ranking Treewidth Parameterized algorithms
CLC: O157.5
Type: Master's thesis
Year: 2010
Downloads: 18
Quote: 0
Read: Download Dissertation

Abstract


The minimum edge (vertex) ranking problem is to find a weight assignment of the edges (vertices) of the input graph with least number of integers such that every path connecting two edges (vertices) with the same weight i contains an intermediate edge (vertex) with weight greater than i. The minimum edge ranking problem has application in scheduling of parallel assembly of a product from its components while the minimum vertex ranking problem plays an important role in computing Cholesky factorization of matrices in parallel, parallel query processing and program verification. Both problems have been proved to be NP-hard for general graphs. However, lots of polynomial-time algorithms exist for the minimum vertex ranking problem on special classes of graphs, such as trees, permutation graphs and interval graphs. Compared with the minimum vertex ranking problem, little is known for the minimum edge ranking problem. Up to now, no polynomial-time algorithm for solving minimum edge ranking problem is known for non-trivial classes of graphs other than trees,2-connected outerplanar graphs and completeκ-partite graphs.In this paper, we are focused on the minimum edge ranking problem on special classes of graphs. In particular, we draw our attention on graphs with bounded treewidth and bounded degree, and propose a polynomial-time algorithm for finding a minimum edge ranking on this special graph class. On the other hand, we also study the minimum edge ranking problem from the perspective of parameterized complexity, and give a fixed-parameter algorithm for its parameterized version. At last we show that the problem is FPT.For minimum edge ranking problem on the class of graphs with bounded treewidth and bounded degree, it can be transferred to the minimum vertex ranking problem on its line graph. With the theorem showing that its line graph has bounded treewidth, we can reuse the polynomial-time algorithm for solving minimum vertex ranking on graphs with bounded treewidth. At a result, we present a polynomial-time algorithm for the original problem.With respect to the parameterized version of minimum edge ranking problem, the parameter is set to be the size of edge ranking. We show that the graph with bounded minimum edge ranking has bounded degree and diameter. With the fact that the degree & diameter problem has a Moore bound, we get a kernel for this parameterized problem. Therefore, we conclude that its parameterized version belongs to FPT class.At the end, we sum up our work on minimum edge ranking problem, and give some suggestions for future research on minimum vertex ranking and minimum edge ranking problem.

Related Dissertations

  1. Research and Extension of the Minimum Labeling Spanning Tree Problem,TP301.6
  2. Figure optimal label criticality , biodegradable and related issues,O157.5
  3. On Ohba’s Conjecture of One Class of Complete Multipartite Graphs,O157.5
  4. Analysis of Complex Networks Modeling and Its Application,O157.5
  5. About two parameters characteristic polynomial and its applications,O157.5
  6. Several studies for scheduling problem,O157.5
  7. Multi-attribute undirected weighted graph clustering method,O157.5
  8. The composite equilibrium existence of the network and its algorithm,O157.5
  9. Random Network Model Discrimination,O157.5
  10. Chromatic Equivalent Graphs of Two Kinds of Graphs,O157.5
  11. The General Methods of Studying the Spectra of Graph,O157.5
  12. The Supply Chain Modeling and Network Efficiency Research Based on Complex Network,O157.5
  13. Complex network reliability evaluation research,O157.5
  14. M (?) Bius cubes crossing number of graphs,O157.5
  15. Local tolerance studies twisted cube LTQ_n,O157.5
  16. Augmented Cubes AQn graph the number of crossing boundaries,O157.5
  17. Tolerant crossedcube study Pancyclicity,O157.5
  18. Local twisted cube graph crossing number of,O157.5
  19. Attack directed repair complex network invulnerability Strategy,O157.5
  20. Hopf Bifurcation and Generalized Synchronization of the Delayed Coupled Lorenz-Rossler Systems,O157.5
  21. Properties of Zero-divisor Graph of Zn[i],O157.5

CLC: > Mathematical sciences and chemical > Mathematics > Algebra,number theory, portfolio theory > Combinatorics ( combinatorics ) > Graph Theory
© 2012 www.DissertationTopic.Net  Mobile