NDLI: Counterexamples for Directed and Node Capacitated Cut-Trees

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Benczr, Andrs A.
Copyright Year	1995
Abstract	We show that there is no cut-tree for various connectivity concepts, hence pointing out errors in the papers of Schnorr [SIAM J. Comput., 8 (1979), pp. 265275] and Gusfield and Naor [Networks, 21 (1991), pp. 505520]. Gomory and Hu [SIAM J. Appl. Math., 9 (1961), pp. 551560] constructed a cut-tree for undirected graphs which compactly represents a minimum cut for each pair of vertices. This has a straightforward generalization to directed Eulerian graphs, cf. Gupta [SIAM J. Appl. Math., 15 (1967), pp. 168171]. A generalization for arbitrary directed graphs was given by Schnorr. There is a well-known transformation of vertex connectivity to directed edge connectivity; directed edge cuts correspond to vertex cuts in some weak sense. The result of Schnorr was later applied by Gusfield and Naor for such a cut-tree construction. In this paper counterexamples are described to show that for directed graphs there is no cut-tree and therefore the cut-tree results of Schnorr and Gusfield and Naor are incorrect. Our final example shows that, without weakening the notion of vertex connectivity, it is impossible to construct vertex cut-trees for undirected graphs in general.
Starting Page	505
Ending Page	510
Page Count	6
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539792236730
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	3
Volume Number	24
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-13
Access Restriction	Subscribed
Subject Keyword	graph connectivity Gomory-Hu trees minimum cuts Network models, deterministic
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in