Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
A linear time algorithm for the minimum weighted feedback vertex set on diamonds
Carrabs F., Cerulli R., Gentili M., Parlato G. Information Processing Letters94 (1):29-35,2005.Type:Article
Date Reviewed: Jan 12 2006

A linear time solution of the weighted feedback vertex problem for diamond graphs is the main contribution of this paper. The result can be obtained from a more general result [1]. There, it is shown that the regarded problem is a linear extended monadic second-order (EMS) extremum problem, and that all such problems can be solved in linear time for classes of graphs of bounded tree-width (see Bodlaender’s paper [2] for a linear-time algorithm for finding a tree decomposition if it is bounded by a fixed parameter). Since it is obvious that diamond graphs have bounded tree width, the result follows from this more general result. Related results can be found in another paper [3].

Reviewer:  D. Seese Review #: CR132292 (0608-0853)
1) Arnborg, S.; Lagergren, J.; Seese, D. Easy problems for tree-decomposable graphs. Journal of Algorithms 12, (1991), 308–340.
2) Bodlaender, H.L. A linear-time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25, (1996), 1305–1317.
3) Courcelle, B.; Makowsky, J.A.; Rotic, U. Linear time solvable optimization problems on graphs of bounded clique-width. Theory Comput. Systems 33, (2000), 125–150.
Bookmark and Share
 
Graph Algorithms (G.2.2 ... )
 
 
Dynamic Programming (I.2.8 ... )
 
 
Graph Labeling (G.2.2 ... )
 
 
Graph Theory (G.2.2 )
 
Would you recommend this review?
yes
no
Other reviews under "Graph Algorithms": Date
Planar graph decomposition and all pairs shortest paths
Frederickson G. (ed) Journal of the ACM 38(1): 162-204, 1991. Type: Article
Oct 1 1991
High probability parallel transitive-closure algorithms
Ullman J., Yannakakis M. SIAM Journal on Computing 20(1): 100-125, 1991. Type: Article
Dec 1 1991
Clique partitions, graph compression and speeding-up algorithms
Feder T., Motwani R.  Theory of computing (, New Orleans, LA, May 6-8, 1991)1331991. Type: Proceedings
Oct 1 1992
more...

E-Mail This Printer-Friendly
Send Your Comments
Contact Us
Reproduction in whole or in part without permission is prohibited.   Copyright 1999-2024 ThinkLoud®
Terms of Use
| Privacy Policy