PLANAR GRAPH ALGORITHMS.

被引：0
|
作者：
Nishizeki, Takao [1 ]
机构：
[1] Tohoku Univ, Dep of Electrical, Communications, Sendai, Jpn, Tohoku Univ, Dep of Electrical Communications, Sendai, Jpn
来源：
Japan Annual Reviews in Electronics, Computers & Telecommunications | 1983年 / 7卷
关键词：
COMPUTER METATHEORY - Programming Theory;
D O I：
暂无
中图分类号：
学科分类号：
摘要：
Recent results are outlined in the development of efficient algorithms for planar graph problems. A linear time 5-coloring algorithm for planar graphs is demonstrated. An O(n log n) time approximation algorithm for the maximum independent set problem on planar graphs is presented. It is shown in a unified way that a large number of combinatorial problems are linear time computable for series-parallel graphs, a class of planar graphs. All algorithms are efficient, say, of O(n) or O(n log n) time complexity and have broad application in various areas of engineering and computer science.
引用
收藏
页码：77 / 91
相关论文
共 50 条
  • [1] GRAPH MONOMORPHISM ALGORITHMS.
    Ghahraman, David E.
    Wong, Andrew K.C.
    Au, Tung
    IEEE Transactions on Systems, Man and Cybernetics, 1980, SMC-10 (04): : 189 - 196
  • [2] PLANAR GRAPH ALGORITHMS
    NISHIZEKI, T
    JAPAN ANNUAL REVIEWS IN ELECTRONICS COMPUTERS & TELECOMMUNICATIONS, 1983, 7 : 77 - 91
  • [3] Approximation algorithms.
    不详
    INTERFACES, 2002, 32 (06) : 96 - 97
  • [4] PARALLEL ALGORITHMS.
    Krinitskii, N.A.
    Programming and Computer Software (English Translation of Programmirovanie), 1983, 9 (04): : 167 - 172
  • [5] BUDDY ALGORITHMS.
    Challab, D.J.
    Roberts, J.D.
    Computer Journal, 1987, 30 (04): : 308 - 315
  • [6] NEW ALGORITHMS FOR PLANAR GRAPH SEPARATION
    DJIDJEV, HN
    DOKLADI NA BOLGARSKATA AKADEMIYA NA NAUKITE, 1988, 41 (01): : 23 - 25
  • [7] XY INTERPOLATION ALGORITHMS.
    Goldberg, Kenneth
    Goldberg, Melvin
    1600, (05):
  • [8] FILE COMPARISON ALGORITHMS.
    Steppe, Tom
    1600, (12):
  • [9] PROGRAMMING CONTROL ALGORITHMS.
    O'Kelly, Darrell
    Mullins, Mark
    1600, (92):
  • [10] Sexy genetic algorithms.
    Burkett, SN
    Clark, RD
    ABSTRACTS OF PAPERS OF THE AMERICAN CHEMICAL SOCIETY, 2000, 219 : U591 - U591
12345