An algorithm for partitioning trees augmented with sibling edges

被引：3

作者：

Bordawekar, Rajesh ^{[1
]}

Shmueli, Oded ^{[2
]}

机构：

[1] IBM TJ Watson Res Ctr, Hawthorne, NY 10532 USA

[2] Technion Israel Inst Technol, Dept Comp Sci, IL-32000 Haifa, Israel

来源：

INFORMATION PROCESSING LETTERS | 2008年 / 108卷 / 03期

关键词：

Algorithms; Analysis of algorithms; Graph algorithms;

D O I：

10.1016/j.ipl.2008.04.010

中图分类号：

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

学科分类号：

0812 ;

摘要：

We investigate a special case of the graph partitioning problem: the partitioning of a sibling graph which is an ordered tree augmented with edges connecting consecutive nodes that share a common parent. We describe the algorithm, XS, and present a proof of its correctness. (C) 2008 Elsevier B.V. All rights reserved.

引用

页码：136 / 142

页数：7