ARBORICITY AND BIPARTITE SUBGRAPH LISTING ALGORITHMS

被引：77
作者：
EPPSTEIN, D
机构：
[1] Department of Information and Computer Science, University of California, Irvine
来源：
INFORMATION PROCESSING LETTERS | 1994年 / 51卷 / 04期
基金：
美国国家科学基金会;
关键词：
ALGORITHM; GRAPH ALGORITHMS;
D O I：
10.1016/0020-0190(94)90121-X
中图分类号：
TP [自动化技术、计算机技术];
学科分类号：
0812 ;
摘要：
In graphs of bounded arboricity, the total complexity of all maximal complete bipartite subgraphs us O(n). We described a linear time algorithm to list such subgraphs. The arboricity bound is necessary: for any constant k and any n there exists and n-vertex graph with P(n) edges and (n/log n)(k) maximal complete bipartite subgraphs K-k,K-l.
引用
收藏
页码：207 / 211
页数：5
相关论文
共 19 条
  • [1] AGARWAL PK, 1993, 9TH P ANN S COMP GEO, P338
  • [2] SIMILARITY SEARCHING IN DATABASES OF 3-DIMENSIONAL MOLECULES AND MACROMOLECULES
    ARTYMIUK, PJ
    BATH, PA
    GRINDLEY, HM
    PEPPERRELL, CA
    POIRRETTE, AR
    RICE, DW
    THORNER, DA
    WILD, DJ
    WILLETT, P
    ALLEN, FH
    TAYLOR, R
    [J]. JOURNAL OF CHEMICAL INFORMATION AND COMPUTER SCIENCES, 1992, 32 (06): : 617 - 630
  • [3] BERN M, 1992, COMPUTING EUCLIDEAN, P23
  • [4] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS
    BOOTH, KS
    LUEKER, GS
    [J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) : 335 - 379
  • [5] GOAL-ORIENTED SUBGRAPH ISOMORPHISM TECHNIQUE FOR IC DEVICE RECOGNITION
    BROWN, AD
    THOMAS, PR
    [J]. IEE PROCEEDINGS-I COMMUNICATIONS SPEECH AND VISION, 1988, 135 (06): : 141 - 150
  • [6] ARBORICITY AND SUBGRAPH LISTING ALGORITHMS
    CHIBA, N
    NISHIZEKI, T
    [J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (01) : 210 - 223
  • [7] PLANAR ORIENTATIONS WITH LOW OUT-DEGREE AND COMPACTION OF ADJACENCY MATRICES
    CHROBAK, M
    EPPSTEIN, D
    [J]. THEORETICAL COMPUTER SCIENCE, 1991, 86 (02) : 243 - 266
  • [8] DILLENCOURT MB, 1992, 8TH P ACM S COMP GEO, P177
  • [9] CONNECTIVITY, GRAPH MINORS, AND SUBGRAPH MULTIPLICITY
    EPPSTEIN, D
    [J]. JOURNAL OF GRAPH THEORY, 1993, 17 (03) : 409 - 416
  • [10] GABOW H, 1988, 20TH ANN ACM S THEOR, P407
12