Title :
The undirected feedback vertex set problem with application to wavelength converter placement on WDM networks
Author :
Yamada, Toshinori ; Tada, Yusuke ; Tanaka, Taka-aki
Author_Institution :
Div. of Math., Electron. & Inf., Saitama Univ., Saitama, Japan
Abstract :
This paper considers a size constrained version of the undirected feedback vertex set problem motivated by placing wavelength converters on a WDM network efficiently, and proves that this problem is NP-complete even in several special cases. Moreover, the paper presents a simple approximation algorithm for a minimization version of the problem using an algorithm for the original minimum undirected feedback vertex set problem.
Keywords :
approximation theory; computational complexity; optimisation; wavelength division multiplexing; NP-complete; WDM networks; minimization version; simple approximation algorithm; undirected feedback vertex set problem; wavelength converter placement; Approximation algorithms; Approximation methods; Circuit synthesis; Integrated circuit modeling; Polynomials; Silicon; WDM networks;
Conference_Titel :
Symbolic and Numerical Methods, Modeling and Applications to Circuit Design (SM2ACD), 2010 XIth International Workshop on
Conference_Location :
Gammath
Print_ISBN :
978-1-4244-6816-4
DOI :
10.1109/SM2ACD.2010.5672317
