An efficient PQ-graph algorithm for solving the graph-realization problem

DOI10.1016/0022-0000(80)90042-2MaRDI QIDQ1142044zbMATH OpenOpenAlexFDO

Authors Satoru Fujishige

Publication date 1980

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0022-0000(80)90042-2

zbMATH Keywords

fundamental circuit matrixgraph-realization problem

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• scientific article; zbMATH DE number 3167398 (Why is no real title available?)
• scientific article; zbMATH DE number 3449757 (Why is no real title available?)
• scientific article; zbMATH DE number 3236772 (Why is no real title available?)
• scientific article; zbMATH DE number 3349475 (Why is no real title available?)
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Converting Linear Programs to Network Problems
• Efficiency of a Good But Not Linear Set Union Algorithm
• From Matrices to Graphs
• Graphs and Vector Spaces
• Network flow, transportation and scheduling. Theory and algorithms
• Synthesis of Switching Functions by Linear Graph Theory
• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms

Cited in

(21)

• On the efficiency of representability tests for matroids
• Characterizing graphic matroids by a system of linear equations
• On the complexity of recognizing directed path families
• Use of hidden network structure in the set partitioning problem
• A characterization of graphic matroids based on circuit orderings
• Integrality properties of edge path tree families
• Intersection graphs of paths in a tree
• The arborescence-realization problem
• Layering strategies for creating exploitable structure in linear and integer programs
• Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested
• Distance realization problems with applications to internet tomography
• A heuristic for finding embedded network structure in mathematical programmes
• Computational implementation of Fujishige's graph realizability algorithm
• Uncovering generalized-network structure in matrices
• Decomposition and optimization over cycles in binary matroids
• Nonseparating Cocircuits in Binary Matroids
• Recognizing Helly edge-path-tree graphs and their clique graphs
• The structure of bases in bicircular matroids
• On the complexity of recognizing a class of generalized networks
• Recognizing hidden bicircular networks
• Implementation of a unimodularity test

This page was built for publication: An efficient PQ-graph algorithm for solving the graph-realization problem

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