Computing Reviews
Today's Issue Hot Topics Search Browse Recommended My Account Log In
Review Help
Search
Profiles of separations: in graphs, matroids, and beyond
Diestel R., Hundertmark F., Lemanczyk S. Combinatorica39 (1):37-75,2019.Type:Article
Date Reviewed: Feb 23 2021

A matroid is a structure of finite nonempty sets of subsets that apply the hereditary property. Here, the authors deploy tree decomposition to distinguish the tangles of a finite graph or matroid. They also apply the Gomory-Hu theorem to edge-tangles. Included are theorems, supported by mathematical proofs, of the canonical graph properties “under the automorphisms of the graph or matroid.” The authors’ “new paradigm” can be applied to “highly connected substructures ... other than graphs,” for example, matroids. Image segmentation and cluster analysis in big datasets are just some of the example applications of the approach presented in this work. After defining abstract separation systems and their profiles, supported with examples, the authors move on to a tangle-tree theorem that is viewed from the perspective of substructure profiles.

The distinguished profiles presented are seen in a “universe of separations.” The authors prove that minimal tree sets can be non-canonical. A section on symmetric tree profiles indicates how to distinguish good triples from bad triples. In section 4, the authors apply their approach to graphs and matroids, understood as “a profile in the universe of all its separations.” The canonical tangle-tree theorem is applied once to graphs and then to matroids. The following section applies the theory to cluster analysis, while edge-tangles and the Gomory-Hu theory are used for graph cut optimization. Section 6 covers “width duality for profiles in graphs.” The article ends with an open problem: how to distinguish arbitrary profiles from block profiles.

Perhaps I can recommend this article to mathematicians working on data clustering, as the research is intriguing to some extent. However, my serious objection is that 12 of the 21 references are written by the authors, meaning that this article is an overview of their work rather than a reliable literature review.

Reviewer:  Jolanta Mizera-Pietraszko Review #: CR147197 (2105-0129)
Bookmark and Share
  Featured Reviewer  
 
Mathematics And Statistics (J.2 ... )
 
 
Graphs And Networks (E.1 ... )
 
Would you recommend this review?
yes
no
Other reviews under "Mathematics And Statistics": Date
Microcomputers and mathematics
Bruce J., Giblin P., Rippon P., Cambridge University Press, New York, NY, 1990. Type: Book (9780521375160)
May 1 1992
Mathographics
Dixon R., Dover Publications, Inc., New York, NY, 1991. Type: Book (9780486266398)
Apr 1 1992
Quaternary quadratic forms
Nipp G., Springer-Verlag New York, Inc., New York, NY, 1991. Type: Book (9780387976013)
Apr 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