Approximability and parameterized complexity of consecutive ones submatrix problems

被引：0

作者：

Dom, Michael ^{[1
]}

Guo, Jiong ^{[1
]}

Niedermeier, Rolf ^{[1
]}

机构：

[1] Univ Jena, Inst Informat, Ernst-Abbe-Platz 2, D-07743 Jena, Germany

来源：

THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, PROCEEDINGS | 2007年 / 4484卷

关键词：

D O I：

暂无

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We develop a refinement of a forbidden submatrix characterization of 0/1-matrices fulfilling the Consecutive Ones Property (C1P). This novel characterization finds applications in new polynomial-time approximation algorithms and fixed-parameter tractability results for the problem to find a, maximum-size submatrix of a 0/1-matrix such that the submatrix has the C1P. Moreover, we achieve a problem kernelization based on simple data reduction rules and provide several search tree algorithms. Finally, we derive inapproximability results.

引用

页码：680 / +

页数：2

共 18 条

[1] [Anonymous], 2004, SODA P 15 ANN ACM SI
[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] On the hardness of approximating minimum vertex cover
Dinur, I
Safra, S
[J]. ANNALS OF MATHEMATICS, 2005, 162 (01) : 439 - 485
[4] DOWNEY R, 1999, PARAMETERIZED COMPLE
[5] Flum J., 2006, Parameterized Complexity Theory
[6] Garey MR, 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness
[7] 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
[8] A note on the Consecutive Ones Submatrix problem
Hajiaghayi, MT
Ganjali, Y
[J]. INFORMATION PROCESSING LETTERS, 2002, 83 (03) : 163 - 166
[9] HAJIAGHAYI MT, 2000, UNPUB CONSECUTIVE ON
[10] Some optimal inapproximability results
Håstad, J
[J]. JOURNAL OF THE ACM, 2001, 48 (04) : 798 - 859

← 1 2 →