Exact algorithms for finding minimum transversals in rank-3 hypergraphs

被引：17
作者：
Wahlström, M [1 ]
机构：
[1] Linkoping Univ, Dept Comp & Informat Sci, TCSLab, Linkoping, Sweden
来源：
JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC | 2004年 / 51卷 / 02期
关键词：
minimum transversal; hypergraph; 3-hitting set; exact algorithm;
D O I：
10.1016/j.jalgor.2004.01.001
中图分类号：
TP301 [理论、方法];
学科分类号：
081202 ;
摘要：
We present two algorithms for the problem of finding a minimum transversal in a hypergraph of rank 3, also known as the 3-Hitting Set problem. This problem is a natural extension of the vertex cover problem for ordinary graphs. The first algorithm runs in time O(1.6538(n)) for a hypergraph with n vertices, and needs polynomial space. The second algorithm uses exponential space and runs in time O(1.6316(n)). (C) 2004 Elsevier Inc. All rights reserved.
引用
收藏
页码：107 / 121
页数：15
相关论文
共 11 条
  • [1] [Anonymous], DIMACS SERIES DISCRE
  • [2] de Caen D., 1983, Ars Combin, V16, P5
  • [3] IDENTIFYING THE MINIMAL TRANSVERSALS OF A HYPERGRAPH AND RELATED PROBLEMS
    EITER, T
    GOTTLOB, G
    [J]. SIAM JOURNAL ON COMPUTING, 1995, 24 (06) : 1278 - 1304
  • [4] On the complexity of dualization of monotone disjunctive normal forms
    Fredman, ML
    Khachiyan, L
    [J]. JOURNAL OF ALGORITHMS, 1996, 21 (03) : 618 - 628
  • [5] Gunopulos D., 1997, Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, PODS 1997, P209, DOI 10.1145/263661.263684
  • [6] Kavvadias DJ, 1999, LECT NOTES COMPUT SC, V1668, P72
  • [7] Approximating coloring and maximum independent sets in 3-uniform hypergraphs
    Krivelevich, M
    Nathaniel, R
    Sudakov, B
    [J]. JOURNAL OF ALGORITHMS-COGNITION INFORMATICS AND LOGIC, 2001, 41 (01): : 99 - 113
  • [8] Mishra N., 1997, Proceedings of the Tenth Annual Conference on Computational Learning Theory, P211, DOI 10.1145/267460.267500
  • [9] Niedermeier R., 2003, Journal of Discrete Algorithms, V1, P89, DOI 10.1016/S1570-8667(03)00009-1
  • [10] ALGORITHMS FOR MAXIMUM INDEPENDENT SETS
    ROBSON, JM
    [J]. JOURNAL OF ALGORITHMS, 1986, 7 (03) : 425 - 440
12