MAXIMUM WEIGHT INDEPENDENT SET IN TREES

被引：3
作者：
PAWAGI, S [1 ]
机构：
[1] SUNY STONY BROOK,DEPT COMP SCI,STONY BROOK,NY 11794
来源：
BIT | 1987年 / 27卷 / 02期
关键词：
D O I：
10.1007/BF01934182
中图分类号：
TP31 [计算机软件];
学科分类号：
081202 ; 0835 ;
摘要：
引用
收藏
页码：170 / 180
页数：11
相关论文
共 50 条
  • [41] SEQUENTIAL AND PARALLEL ALGORITHMS FOR THE MAXIMUM-WEIGHT INDEPENDENT SET PROBLEM ON PERMUTATION GRAPHS
    YU, MS
    TSENG, LY
    CHANG, SJ
    INFORMATION PROCESSING LETTERS, 1993, 46 (01) : 7 - 11
  • [42] Boosting Data Reduction for the Maximum Weight Independent Set Problem Using Increasing Transformations
    Gellner, Alexander
    Lamm, Sebastian
    Schulz, Christian
    Strash, Darren
    Zavalnij, Bogdan
    2021 PROCEEDINGS OF THE SYMPOSIUM ON ALGORITHM ENGINEERING AND EXPERIMENTS, ALENEX, 2021, : 128 - 142
  • [43] Distributed Approximation of Maximum Independent Set and Maximum Matching
    Bar-Yehuda, Reuven
    Censor-Hillel, Keren
    Ghaffari, Mohsen
    Schwartzman, Gregory
    PROCEEDINGS OF THE ACM SYMPOSIUM ON PRINCIPLES OF DISTRIBUTED COMPUTING (PODC'17), 2017, : 165 - 174
  • [44] Belief propagation for the maximum-weight independent set and minimum spanning tree problems
    Cornelissen, Kamiel
    Manthey, Bodo
    THEORETICAL COMPUTER SCIENCE, 2018, 738 : 53 - 64
  • [45] An efficient algorithm for finding a maximum weight k-independent set on trapezoid graphs
    Hota, M
    Pal, M
    Pal, TK
    COMPUTATIONAL OPTIMIZATION AND APPLICATIONS, 2001, 18 (01) : 49 - 62
  • [46] PTAS for maximum weight independent set problem with random weights in bounded degree graphs
    Gamarnik, David
    Goldberg, David
    Weber, Theophane
    PROCEEDINGS OF THE TWENTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS, 2010, 135 : 268 - 278
  • [47] An Efficient Algorithm for Finding a Maximum Weight k-Independent Set on Trapezoid Graphs
    Mrinmoy Hota
    Madhumangal Pal
    Tapan K. Pal
    Computational Optimization and Applications, 2001, 18 : 49 - 62
  • [48] A sequential algorithm for finding a maximum weight K-independent set on interval graphs
    Pal, M
    Bhattacharjee, GP
    INTERNATIONAL JOURNAL OF COMPUTER MATHEMATICS, 1996, 60 (3-4) : 205 - 214
  • [49] On Approximating Maximum Independent Set of Rectangles
    Chuzhoy, Julia
    Ene, Alina
    2016 IEEE 57TH ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS), 2016, : 820 - 829
  • [50] MAXIMUM SIZE OF AN INDEPENDENT SET IN A GRAPH
    ALBERTSON, MO
    HUTCHINSON, JP
    NOTICES OF THE AMERICAN MATHEMATICAL SOCIETY, 1975, 22 (01): : A39 - A40
12345