Minimum cycle bases of weighted outerplanar graphs

被引：1
作者：
Liu, Tsung-Hao [1 ]
Lu, Hsueh-I [1 ]
机构：
[1] Natl Taiwan Univ, Dept Comp Sci & Informat Engn, Taipei, Taiwan
来源：
INFORMATION PROCESSING LETTERS | 2010年 / 110卷 / 21期
关键词：
Graph algorithms; Minimum cycle basis; Outerplanar graph; DIRECT PRODUCTS; ALGORITHM;
D O I：
10.1016/j.ipl.2010.08.005
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
We give the first optimal algorithm that computes a minimum cycle basis for any weighted outerplanar graph. Specifically, for any n-node edge-weighted outerplanar graph G, we give an O(n)-time algorithm to obtain an O(n)-space compact representation Z(C) for a minimum cycle basis C of G. Each cycle in C can be computed from Z(C) in O(1) time per edge. Our result works for directed and undirected outerplanar graphs G. (C) 2010 Elsevier B.V. All rights reserved.
引用
收藏
页码：970 / 974
页数：5
相关论文
共 25 条
[1]  
Amaldi E, 2009, LECT NOTES COMPUT SC, V5757, P301, DOI 10.1007/978-3-642-04128-0_28
[2]   Minimum cycle bases for network graphs [J].
Berger, F ;
Gritzmann, P ;
de Vries, S .
ALGORITHMICA, 2004, 40 (01) :51-62
[3]   MATRIX MULTIPLICATION VIA ARITHMETIC PROGRESSIONS [J].
COPPERSMITH, D ;
WINOGRAD, S .
JOURNAL OF SYMBOLIC COMPUTATION, 1990, 9 (03) :251-280
[4]  
de Pina J. C., 1995, Applications of shortest path methods
[5]   DESIGNING NETWORKS WITH COMPACT ROUTING TABLES [J].
FREDERICKSON, GN ;
JANARDAN, R .
ALGORITHMICA, 1988, 3 (01) :171-190
[6]  
Golynski A, 2002, LECT NOTES COMPUT SC, V2368, P200
[7]  
Hammack R, 2006, AUSTRALAS J COMB, V36, P213
[8]   Minimum cycle bases of direct products of complete graphs [J].
Hammack, Richard .
INFORMATION PROCESSING LETTERS, 2007, 102 (05) :214-218
[9]   THE ALL-PAIRS MIN CUT PROBLEM AND THE MINIMUM CYCLE BASIS PROBLEM ON PLANAR GRAPHS [J].
HARTVIGSEN, D ;
MARDON, R .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 1994, 7 (03) :403-418
[10]   A POLYNOMIAL-TIME ALGORITHM TO FIND THE SHORTEST CYCLE BASIS OF A GRAPH [J].
HORTON, JD .
SIAM JOURNAL ON COMPUTING, 1987, 16 (02) :358-366
123