On the complexity of recognizing a class of generalized networks

DOI10.1016/0167-6377(85)90036-7MaRDI QIDQ1058995zbMATH OpenOpenAlexFDO

Authors Vijaya Chandru, Collette R. Coullard, Donald K. Wagner

Publication date 1985

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0167-6377(85)90036-7

zbMATH Keywords

computational complexitygeneralized network flow problemmatroidproblem equivalenceproblem transformationunit-weight cycles

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Analysis of algorithms and problem complexity (68Q25) Deterministic network models in operations research (90B10) Linear programming (90C05) Integer programming (90C10) Programming involving graphs or networks (90C35)

Review text

The problem of determining whether a given linear programming problem can be converted to a generalized network flow problem having no unit-weight cycles is shown to be NP-hard. The same argument also shows that the problem of determining whether a gain matroid is bicircular is NP-hard.

Recommendations

• Recognizing hidden bicircular networks
• scientific article; zbMATH DE number 3878637
• Extracting embedded generalized networks from linear programming problems
• The structure of bases in bicircular matroids
• Uncovering generalized-network structure in matrices

Cites work

• A note on detecting simple redundancies in linear systems
• An efficient PQ-graph algorithm for solving the graph-realization problem
• An efficient scaling procedure for gain networks
• Connectivity in bicircular matroids
• Converting Linear Programs to Network Problems
• Graph theory
• scientific article; zbMATH DE number 3791941 (Why is no real title available?)
• scientific article; zbMATH DE number 3534506 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Voltage-graphic matroids

Cited in

(6)

• Characterizing bias matroids
• Recognizing hidden bicircular networks
• Uncovering generalized-network structure in matrices
• Recognizing a class of bicircular matroids
• Generalized networks: the theory of preprocessing and an empirical analysis
• The structure of bases in bicircular matroids

This page was built for publication: On the complexity of recognizing a class of generalized networks

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