Reducing Rank of the Adjacency Matrix by Graph Modification

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

Mathematics Subject Classification ID

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

Matrix Rigidity from the Viewpoint of Parameterized Complexity

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