THE COMPUTATIONAL COMPLEXITY OF AVOIDING FORBIDDEN SUBMATRICES BY ROW DELETIONS
DOI10.1142/S0129054106004522zbMath1169.68559OpenAlexW2143199097MaRDI QIDQ3421857
Jochen Alber, Jens Gramm, Sebastian Wernicke, Jiong Guo, Rolf Niedermeier
Publication date: 8 February 2007
Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1142/s0129054106004522
NP-completefixed-parameter tractabilityhitting setforbidden submatrixpolynomial-time constant-factor approximation
Analysis of algorithms and problem complexity (68Q25) Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Approximation algorithms (68W25)
Cites Work
- Unnamed Item
- Unnamed Item
- Graph-modeled data clustering: Exact algorithms for clique generation
- Parameterized enumeration, transversals, and imperfect phylogeny reconstruction
- An efficient fixed-parameter algorithm for 3-hitting set
- The node-deletion problem for hereditary properties is NP-complete
- Automated generation of search tree algorithms for hard graphs modification problems
- Cluster graph modification problems
- Permuting matrices to avoid forbidden submatrices
- Node-Deletion Problems on Bipartite Graphs
- Graph Classes: A Survey
- Incomplete Directed Perfect Phylogeny
- Applications of approximation algorithms to cooperative games
- Complexity classification of some edge modification problems
