Memory efficient algorithms for cactus graphs and block graphs

被引：8

作者：

Brimkov, Boris ^{[1
]}

Hicks, Illya V. ^{[1
]}

机构：

[1] Rice Univ, Computat & Appl Math, Houston, TX 77005 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2017年 / 216卷

基金：

美国国家科学基金会;

关键词：

Constant-work-space algorithm; In-place algorithm; Shortest path; Cactus graph; Block graph; Chromatic polynomial; SPACE ALGORITHMS;

D O I：

10.1016/j.dam.2015.10.032

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

We present constant-work-space polynomial time algorithms for solving the shortest path problem, finding the chromatic polynomial, clique number, number of components, circumference, and girth of cactus graphs and block graphs. For some of these problems we also present in-place algorithms, which perform faster than the corresponding constant work-space algorithms. The problems considered are fundamental to many areas of graph theory, computational geometry, and combinatorial optimization, and have a wide range of applications including transportation, robotics, and image processing. (C) 2015 Elsevier B.V. All rights reserved.

引用

页码：393 / 407

页数：15

共 35 条

[1]

[Anonymous], 1975, P 16 ANN IEEE S FDN

[2]

Asano Tetsuo, 2011, Journal of Graph Algorithms and Applications, V15, P569, DOI 10.7155/jgaa.00240

[3]

ASANO T, 2008, P 1 AAAC ANN M HONG, P3

[4]

Asano T, 2009, P 24 EUR WORKSH COMP, P165

[5]

Asano T., 2008, LNCS, V5369, P1

[6]

Asano T, 2009, LECT NOTES COMPUT SC, V5416, P268

[7]

Barnes G., 1993, Proceedings of the Twenty-Fifth Annual ACM Symposium on the Theory of Computing, P728, DOI 10.1145/167088.167275

[8] Enumeration of m-ary cacti [J].

Bóna, M ;

Bousquet, M ;

Labelle, G ;

Leroux, P .

ADVANCES IN APPLIED MATHEMATICS, 2000, 24 (01) :22-56

[9] Space-efficient geometric divide-and-conquer algorithms [J].

Bose, Prosenjit ;

Maheshwari, Anil ;

Morin, Pat ;

Morrison, Jason ;

Smid, Michiel ;

Vahrenhold, Jan .

COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS, 2007, 37 (03) :209-227

[10]

Brimkov B, 2013, LECT NOTES COMPUT SC, V8033, P476, DOI 10.1007/978-3-642-41914-0_47

← 1 2 3 4 →