Extracting pure network submatrices in linear programs using signed graphs.

DOI10.1016/S0166-218X(03)00361-5zbMath1095.90112OpenAlexW1994941014MaRDI QIDQ1427813

Gautam Mitra, Nalân Gülpinar, Gregory Gutin, Alexey Zverovich

Publication date: 14 March 2004

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0166-218x(03)00361-5

zbMATH Keywords

NetworksSigned graphsLinear programs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Linear programming (90C05) Approximation methods and heuristics in mathematical programming (90C59) Signed and weighted graphs (05C22)

Related Items (12)

A heuristic based on negative chordless cycles for the maximum balanced induced subgraph problem ⋮ Cycle-based reducibility of multi-index transport-type systems of linear inequalities ⋮ Multiindex transportation problems with 2-embedded structure ⋮ A branch-and-cut algorithm for the maximum \(k\)-balanced subgraph of a signed graph ⋮ Maximum balanced subgraph problem parameterized above lower bound ⋮ Evaluating balancing on social networks through the efficient solution of correlation clustering problems ⋮ Three-index linear programs with nested structure ⋮ Multi-index transportation problems with 1-nested structure ⋮ Multi-index transport problems with decomposition structure ⋮ An exact approach to the problem of extracting an embedded network matrix ⋮ Fixed-Parameter Algorithms in Analysis of Heuristics for Extracting Networks in Linear Programs ⋮ The maximum balanced subgraph of a signed graph: applications and solution approaches

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Iterative improvement of vertex covers
• How colorful the signed graph?
• 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
• A mathematical bibliography of signed and gain graphs and allied areas
• Glossary of signed and gain graphs and allied areas
• Detecting embedded networks in LP using GUB structures and independent set algorithms
• A good submatrix is hard to find
• On the notion of balance of a signed graph
• The Elimination form of the Inverse and its Application to Linear Programming
• Automatic identification of embedded network rows in large-scale optimization models
• Finding Embedded Network Rows in Linear Programs I. Extraction Heuristics
• Converting Linear Programs to Network Problems
• Automatic Identification of Generalized Upper Bounds in Large-Scale Optimization Models
• Analysis of mathematical programming problems prior to applying the simplex algorithm

This page was built for publication: Extracting pure network submatrices in linear programs using signed graphs.