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

DOI10.1016/0022-0000(80)90042-2zbMath0438.68028OpenAlexW1990118448MaRDI QIDQ1142044

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

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

Related Items

Intersection graphs of paths in a tree, Decomposition and optimization over cycles in binary matroids, 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, Use of hidden network structure in the set partitioning problem, Implementation of a unimodularity test, The structure of bases in bicircular matroids, Characterizing graphic matroids by a system of linear equations, A Characterization of Graphic Matroids Based on Circuit Orderings, Recognizing hidden bicircular networks, On the complexity of recognizing directed path families, Recognizing Helly edge-path-tree graphs and their clique graphs, A heuristic for finding embedded network structure in mathematical programmes, On the efficiency of representability tests for matroids, Integrality properties of edge path tree families, Computational implementation of Fujishige's graph realizability algorithm, On the complexity of recognizing a class of generalized networks, Uncovering generalized-network structure in matrices, Nonseparating Cocircuits in Binary Matroids, Distance realization problems with applications to internet tomography

Cites Work

• Testing for the consecutive ones property, interval graphs, and graph planarity using PQ-tree algorithms
• Network flow, transportation and scheduling. Theory and algorithms
• Graphs and Vector Spaces
• An Algorithm for Determining Whether a Given Binary Matroid is Graphic
• Synthesis of Switching Functions by Linear Graph Theory
• Converting Linear Programs to Network Problems
• Efficiency of a Good But Not Linear Set Union Algorithm
• From Matrices to Graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item