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 条
  • [21] CONSTRUCTION AND INTERPRETATION OF FUZZY ALGORITHMS.
    Balashov, Ye.P.
    Kupriyanov, M.S.
    Loginskaya, L.G.
    1600, (24):
  • [22] DECISION TABLES AND DECISION ALGORITHMS.
    Pawlak, Zdzislaw
    1600, (33): : 9 - 10
  • [23] ELECTRONIC CIRCUIT LAYOUT ALGORITHMS.
    Soukup, Jiri
    Telesis Ottawa, 1980, 7 (02): : 11 - 16
  • [24] Two Separation Problem Algorithms.
    Taukchi, V.M.
    Izvestia vyssih ucebnyh zavedenij. Priborostroenie, 1981, 24 (01): : 89 - 93
  • [25] COMPARING SEISMIC MODELING ALGORITHMS.
    Cline, W.Michael
    1600, (84):
  • [26] PARALLEL Sn TRANSPORT ALGORITHMS.
    Wienke, B.R.
    Hiromoto, R.E.
    Transport Theory and Statistical Physics, 1986, 15 (1-2): : 49 - 59
  • [27] On iterative algorithms. II.
    Geppert, H
    MATHEMATISCHE ANNALEN, 1933, 108 : 197 - 207
  • [28] BROADCAST COMMUNICATIONS AND DISTRIBUTED ALGORITHMS.
    Dechter, Rina
    Kleinrock, Leonard
    IEEE Transactions on Computers, 1986, C-35 (03) : 210 - 219
  • [29] LOGIC SCHEMES OF PROGRAMS AND ALGORITHMS.
    Krinitskii, N.A.
    Programming and Computer Software (English Translation of Programmirovanie), 1980, 6 (03): : 119 - 128
  • [30] ANALYSIS OF GRID FILE ALGORITHMS.
    Regnier, Mireille
    BIT (Copenhagen), 1985, 25 (02): : 335 - 357
12345