A Square Time Algorithm for Cyclic Edge Connectivity of Planar Graphs

被引：0
作者：
Lou, Dingjun [1 ]
机构：
[1] Sun Yat Sen Univ, Dept Comp Sci, Guangzhou 510275, Guangdong, Peoples R China
来源：
ARS COMBINATORIA | 2017年 / 133卷
关键词：
Square time algorithm; cyclic edge connectivity; planar graph; REGULAR GRAPHS;
D O I：
暂无
中图分类号：
O1 [数学];
学科分类号：
0701 ; 070101 ;
摘要：
In this paper, we introduce an O(n(2)) time algorithm to determine the cyclic edge connectivity of a planar graph, where n is the order of the planar graph. This is the first correct square time algorithm for cyclic edge connectivity of planar graphs.
引用
收藏
页码：69 / 92
页数：24
相关论文
共 14 条
  • [1] Aho A., 1976, DESIGN ANAL COMPUTER
  • [2] Bondy J.A., 2007, Citeseer
  • [3] Dvorák Z, 2004, LECT NOTES COMPUT SC, V3111, P236
  • [4] ON THE 2-EXTENDIBILITY OF PLANAR GRAPHS
    HOLTON, DA
    LOU, DJ
    PLUMMER, MD
    [J]. DISCRETE MATHEMATICS, 1991, 96 (02) : 81 - 99
  • [5] Characterization of graphs with infinite cyclic edge connectivity
    Lou, Dingjun
    Wang, Wei
    [J]. DISCRETE MATHEMATICS, 2008, 308 (11) : 2094 - 2103
  • [6] Lou DJ, 2005, ARS COMBINATORIA, V77, P311
  • [7] LOWER BOUND OF CYCLIC EDGE CONNECTIVITY FOR N-EXTENDABILITY OF REGULAR GRAPHS
    LOU, DJ
    HOLTON, DA
    [J]. DISCRETE MATHEMATICS, 1993, 112 (1-3) : 139 - 150
  • [8] An Efficient Algorithm for Cyclic Edge Connectivity of Planar Graphs
    Lu, Yunting
    Lu, Xin
    [J]. 2009 ASIA-PACIFIC CONFERENCE ON INFORMATION PROCESSING (APCIP 2009), VOL 2, PROCEEDINGS, 2009, : 193 - 195
  • [9] COMPUTING EDGE-CONNECTIVITY IN MULTIGRAPHS AND CAPACITATED GRAPHS
    NAGAMOCHI, H
    IBARAKI, T
    [J]. SIAM JOURNAL ON DISCRETE MATHEMATICS, 1992, 5 (01) : 54 - 66
  • [10] Nedela R., 1995, MATH SLOVACA, V45, P481
12