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 complexitymatroidgeneralized network flow problemproblem equivalenceproblem transformationunit-weight cycles

Mathematics Subject Classification ID

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

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

• 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?)
• 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
• Voltage-graphic matroids

Cited in

(6)

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

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)