Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs

DOI10.1007/978-3-642-11269-0_18zbMath1273.68175OpenAlexW1487079463MaRDI QIDQ3656864

Igor Razgon, Gregory Gutin, Daniel Karapetyan

Publication date: 14 January 2010

Published in: Parameterized and Exact Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-642-11269-0_18

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Linear programming (90C05)

Related Items (4)

A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ Vertex cover problem parameterized above and below tight bounds ⋮ Acyclic Digraphs ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Finding odd cycle transversals.
• Almost 2-SAT is fixed-parameter tractable
• Signed graphs
• A simple algorithm to detect balance in signed graphs
• A \((\Delta / 2)\)-approximation algorithm for the maximum independent set problem
• A heuristic for finding embedded network structure in mathematical programmes
• Extracting pure network submatrices in linear programs using signed graphs.
• Detecting embedded networks in LP using GUB structures and independent set algorithms
• A good submatrix is hard to find
• Crown structures for vertex cover kernelization
• Parametrized complexity theory.
• Scalable parallel algorithms for FPT problems
• Linear Inequalities and Related Systems. (AM-38)
• Automatic identification of embedded network rows in large-scale optimization models
• Computation of Renameable Horn Backdoors
• Algorithm Engineering for Optimal Graph Bipartization
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• Converting Linear Programs to Network Problems
• Algorithmic and Complexity Results for Decompositions of Biological Networks into Monotone Subsystems
• Optimal Edge Deletions for Signed Graph Balancing

This page was built for publication: Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs