A counterexample for the proof of implication conjecture on independent spanning trees

被引：8

作者：

Gopalan, Abishek ^{[1
]}

Ramasubramanian, Srinivasan ^{[1
]}

机构：

[1] Univ Arizona, Dept Elect & Comp Engn, Tucson, AZ 85721 USA

来源：

INFORMATION PROCESSING LETTERS | 2013年 / 113卷 / 14-16期

基金：

美国国家科学基金会;

关键词：

Independent trees; Spanning trees; Three connectivity; Graph algorithms;

D O I：

10.1016/j.ipl.2013.04.008

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

Khuller and Schieber (1992) in [1] developed a constructive algorithm to prove that the existence of k-vertex independent trees in a k-vertex connected graph implies the existence of k-edge independent trees in a k-edge connected graph. In this paper, we show a counterexample where their algorithm fails. (C) 2013 Elsevier B.V. All rights reserved.

引用

页码：522 / 526

页数：5