Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Finding the t-join structure of graphs
Sebö A. Mathematical Programming: Series A36 (2):123-134,1986.Type:Article
Date Reviewed: Sep 1 1988

This is a theoretical research paper of interest for experts in graph algorithms, particularly matching and postman tours. Its goal is to give a new setting for, or to revisit, such classics as the Chinese postman problem as originally dealt with by Guan [1] or the well-known matching algorithm of Edmonds, as approached by Lovász [2]. For this purpose, the author uses the concept of a t-join in an undirected graph. As he points out, t-joins are generalizations of postman tours, matchings, and paths. t-cuts are naturally associated with t-joins. The author’s main result is a polynomial-time combinatorial algorithm that determines a minimum t-join and a so-called canonical (maximum) packing of t-cuts.

A pertinent list of references is included in the paper. The paper will have appeal for those who are knowledgeable about the topic but will be difficult for the non-expert to read.

Reviewer:  J. M. S. Simoões-Pereira Review #: CR111689
1) Guan, M. G.Graphic programming using odd or even points. Chin Math. 1 (1962), 273–277.
2) Lova:9awsz, L.2-matchings and 2-covers of hypergraphs. Acta Math. Acad. Sci. Hung. 26 (1975), 433–444.
Bookmark and Share
 
Path And Circuit Problems (G.2.2 ... )
 
 
Combinatorial Algorithms (G.2.1 ... )
 
 
Graph Algorithms (G.2.2 ... )
 
 
Minimax Approximation And Algorithms (G.1.2 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Path And Circuit Problems": Date
Hypermap rewriting
Sopena E. Theoretical Computer Science 85(2): 253-281, 1991. Type: Article
Jun 1 1992
Optimal covering of cacti by vertex-disjoint paths
Moran S., Wolfsthal Y. Theoretical Computer Science 84(2): 179-197, 1991. Type: Article
Mar 1 1993
&agr;-vertex separator is NP-hard even for 3-regular graphs
Müller R., Wagner D. Computing 46(4): 343-353, 1991. Type: Article
Dec 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