On the complexity of the eigenvalue deletion problem

DOI10.4230/LIPICS.ISAAC.2023.53MaRDI QIDQ6953161zbMATH OpenFDO

Authors Neeldhara Misra, Harshil Mittal, Saket Saurabh, Dhara Thakkar

Publication date 24 July 2025

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.4230/LIPICS.ISAAC.2023.53

zbMATH Keywords

eigenvaluesrank reductiongraph modification

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx)

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1496857 (Why is no real title available?)
• Algorithms and complexity of \(s\)-club cluster vertex deletion
• Cluster graph modification problems
• Computing a maximum cardinality matching in a bipartite graph in time \(O(n^{1,5}\sqrt{m/\log \,n})\)
• Geometric versions of the three-dimensional assignment problem under general norms
• On characterizing certain graphs with four eigenvalues by their spectra
• On split graphs with four distinct eigenvalues
• Paths, Trees, and Flowers
• Rank reduction of oriented graphs by vertex and edge deletions
• Reducing rank of the adjacency matrix by graph modification

Cited in

(1)

• Parameterized algorithms for editing to uniform cluster graph

This page was built for publication: On the complexity of the eigenvalue deletion problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6953161)