Certifying algorithms for recognizing interval graphs and permutation graphs

被引：48

作者：

Kratsch, Dieter ^{[1
]}

McConnell, Ross M.

Mehlhorn, Kurt

Spinrad, Jeremy P.

机构：

[1] Univ Metz, LITA, F-57045 Metz 01, France

[2] Colorado State Univ, Dept Comp Sci, Ft Collins, CO 80523 USA

[3] Max Planck Inst Informat, D-66123 Saarbrucken, Germany

[4] Vanderbilt Univ, Dept Elect Engn & Comp Sci, Nashville, TN 37235 USA

来源：

SIAM JOURNAL ON COMPUTING | 2006年 / 36卷 / 02期

关键词：

certificates; certifying algorithms; interval graphs; permutation graphs;

D O I：

10.1137/S0097539703437855

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

A certifying algorithm for a problem is an algorithm that provides a certificate with each answer that it produces. The certificate is a piece of evidence that proves that the answer has not been compromised by a bug in the implementation. We give linear-time certifying algorithms for recognition of interval graphs and permutation graphs, and for a few other related problems. Previous algorithms fail to provide supporting evidence when they claim that the input graph is not a member of the class. We show that our certificates of nonmembership can be authenticated in O(vertical bar V vertical bar) time.

引用

页码：326 / 353

页数：28

共 28 条

[1] Blum M., 1989, Proceedings of the Twenty First Annual ACM Symposium on Theory of Computing, P86, DOI 10.1145/73007.73015
[2] TESTING FOR CONSECUTIVE ONES PROPERTY, INTERVAL GRAPHS, AND GRAPH PLANARITY USING PQ-TREE ALGORITHMS
BOOTH, KS
LUEKER, GS
[J]. JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1976, 13 (03) : 335 - 379
[3] BRANDSTADT A, 1999, SIAM MONOGR DISCRETE, V3
[4] Corneil D.G., 1998, Symposium on Discrete Algorithms, P175
[5] A LINEAR RECOGNITION ALGORITHM FOR COGRAPHS
CORNEIL, DG
PERL, Y
STEWART, LK
[J]. SIAM JOURNAL ON COMPUTING, 1985, 14 (04) : 926 - 934
[6] Dirac G. A., 1961, Abh. Math. Semin. Univ. Hambg, V25, P71, DOI [10.1007/BF02992776, DOI 10.1007/BF02992776]
[7] TRANSITIV ORIENTIERBARE GRAPHEN
GALLAI, T
[J]. ACTA MATHEMATICA ACADEMIAE SCIENTIARUM HUNGARICAE, 1967, 18 (1-2): : 25 - &
[8] Golumbic MC., 1980, Algorithmic Graph Theory and Perfect Graphs
[9] Lex-BFS and partition refinement, with applications to transitive orientation, interval graph recognition and consecutive ones testing
Habib, M
McConnell, R
Paul, C
Viennot, L
[J]. THEORETICAL COMPUTER SCIENCE, 2000, 234 (1-2) : 59 - 84
[10] FAST ALGORITHMS FOR FINDING NEAREST COMMON ANCESTORS
HAREL, D
TARJAN, RE
[J]. SIAM JOURNAL ON COMPUTING, 1984, 13 (02) : 338 - 355

← 1 2 3 →