Simultaneous consecutive ones submatrix and editing problems: classical complexity and fixed-parameter tractable results
DOI10.1016/j.tcs.2019.05.043zbMath1435.68222arXiv1707.00106OpenAlexW2954021425WikidataQ127553174 ScholiaQ127553174MaRDI QIDQ2297848
Mohith Jagalmohanan, Rani M. R, Subashini R
Publication date: 20 February 2020
Published in: Theoretical Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1707.00106
parameterized complexityfixed-parameter tractable (FPT)consecutive-ones property (C1P)simultaneous consecutive-ones property (SC1P)
Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Combinatorics in computer science (68R05) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Chordal editing is fixed-parameter tractable
- Fundamentals of parameterized complexity
- A faster algorithm for finding minimum Tucker submatrices
- Approximation and fixed-parameter algorithms for consecutive ones submatrix problems
- The simultaneous consecutive ones problem
- Interval graphs and interval orders
- Efficient algorithms for finding maximum matchings in convex bipartite graphs and related problems
- Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
- On the consecutive ones property
- PC trees and circular-ones arrangements.
- Hardness results on the gapped consecutive-ones property problem
- Proper interval vertex deletion
- On the threshold of intractability
- Obtaining matrices with the consecutive ones property by row deletions
- Incidence matrices and interval graphs
- A structure theorem for the consecutive 1's property
- On the Gapped Consecutive-Ones Property
- Faster and Simpler Minimal Conflicting Set Identification
- A Polynomial-Time Algorithm for Finding a Minimal Conflicting Set Containing a Given Row
- Consecutive Ones Property Testing: Cut or Swap
- A Simple Test for the Consecutive Ones Property
- A Faster Algorithm for Finding Minimum Tucker Submatrices
- Node-Deletion Problems on Bipartite Graphs
- Computing the Minimum Fill-In is NP-Complete
- Tractability of Parameterized Completion Problems on Chordal, Strongly Chordal, and Proper Interval Graphs
- Linear Recognition of Almost Interval Graphs
- Node-and edge-deletion NP-complete problems
- On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
- Complexity classification of some edge modification problems
