Rank reduction of oriented graphs by vertex and edge deletions

DOI10.1007/s00453-017-0340-2zbMath1391.68091OpenAlexW2897057216MaRDI QIDQ722520

Saket Saurabh, Syed M. Meesum

Publication date: 26 July 2018

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-017-0340-2

zbMATH Keywords

oriented graphparameterized complexityfixed parameter tractablevertex deletionedge deletionrank of skew-adjacency matrix

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) Directed graphs (digraphs), tournaments (05C20)

Related Items (1)

A survey of parameterized algorithms and the complexity of edge modification

Cites Work

• Unnamed Item
• Unnamed Item
• Bicyclic oriented graphs with skew-rank 2 or 4
• Chordal editing is fixed-parameter tractable
• Reducing rank of the adjacency matrix by graph modification
• Skew-adjacency matrices of graphs
• Unit interval editing is fixed-parameter tractable
• A kernelization algorithm for \(d\)-hitting set
• The node-deletion problem for hereditary properties is NP-complete
• A unified approximation algorithm for node-deletion problems
• The maximum edge biclique problem is NP-complete
• A polynomial kernel for trivially perfect editing
• On the threshold of intractability
• On the complexity of matrix rank and rigidity
• Faster parameterized algorithms for deletion to split graphs
• Tight bounds for parameterized complexity of cluster editing with a small number of clusters
• Exploring the Subexponential Complexity of Completion Problems
• Finding small separators in linear time via treewidth reduction
• Extremal Combinatorics
• On the hardness of approximating minimization problems
• Linear Recognition of Almost Interval Graphs
• Subexponential parameterized algorithm for Interval Completion
• Lower bounds for the parameterized complexity of Minimum Fill-In and other completion problems
• 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
• Parameterized Algorithms
• Editing the Simplest Graphs
• A Subexponential Parameterized Algorithm for Proper Interval Completion

This page was built for publication: Rank reduction of oriented graphs by vertex and edge deletions