Reducing Rank of the Adjacency Matrix by Graph Modification
From MaRDI portal
Publication:3196399
DOI10.1007/978-3-319-21398-9_29zbMath1394.68268OpenAlexW2261794523MaRDI QIDQ3196399
Pranabendu Misra, Saket Saurabh, Syed M. Meesum
Publication date: 29 October 2015
Published in: Lecture Notes in Computer Science (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/978-3-319-21398-9_29
Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85)
Related Items
Cites Work
- Finding odd cycle transversals.
- Fixed-parameter algorithms for cluster vertex deletion
- The node-deletion problem for hereditary properties is NP-complete
- Fixed-parameter tractability of graph modification problems for hereditary properties
- The maximum edge biclique problem is NP-complete
- Cluster graph modification problems
- Graph minors. XIII: The disjoint paths problem
- Tight bounds for parameterized complexity of cluster editing with a small number of clusters
- NP-completeness results for edge modification problems
- Chordal Editing is Fixed-Parameter Tractable
- Extremal Combinatorics
- A More Effective Linear Kernelization for Cluster Editing
- The rank and size of graphs
- Interval Deletion Is Fixed-Parameter Tractable
- Node-and edge-deletion NP-complete problems
- Subexponential Parameterized Algorithm for Minimum Fill-In
- Editing the Simplest Graphs