An Almost Linear-Time Algorithm for Graph Realization

DOI10.1287/moor.13.1.99zbMath0654.05023OpenAlexW2170668134MaRDI QIDQ3800056

Donald K. Wagner, Robert E. Bixby

Publication date: 1988

Published in: Mathematics of Operations Research (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1911/101579

zbMATH Keywords

treealgorithmnetwork structureplanarity testinggraph-realization problem

Mathematics Subject Classification ID

Trees (05C05) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08)

Related Items

On computing the Galois lattice of bipartite distance hereditary graphs ⋮ Decomposition and optimization over cycles in binary matroids ⋮ The arborescence-realization problem ⋮ Recognizing binet matrices ⋮ Exact algorithms and applications for tree-like Weighted Set Cover ⋮ Layering strategies for creating exploitable structure in linear and integer programs ⋮ Independence and port oracles for matroids, with an application to computational learning theory ⋮ Personal reminiscence: combinatorial and discrete optimization problems in which I have been interested ⋮ Twins in Subdivision Drawings of Hypergraphs ⋮ The structure of bases in bicircular matroids ⋮ Characterizing graphic matroids by a system of linear equations ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees, with applications to matching and set cover ⋮ A Characterization of Graphic Matroids Based on Circuit Orderings ⋮ Bond graphs. III: Bond graphs and electrical networks ⋮ Primal-dual approximation algorithms for integral flow and multicut in trees ⋮ Locating facilities which interact: Some solvable cases ⋮ Recognizing hidden bicircular networks ⋮ On the complexity of recognizing directed path families ⋮ Recognizing Helly edge-path-tree graphs and their clique graphs ⋮ C-planarity testing of embedded clustered graphs with bounded dual carving-width ⋮ A heuristic for finding embedded network structure in mathematical programmes ⋮ Future paths for integer programming and links to artificial intelligence ⋮ On testing consecutive-ones property in parallel ⋮ Integrality properties of edge path tree families ⋮ Vertex covering by paths on trees with its applications in machine translation ⋮ Computational implementation of Fujishige's graph realizability algorithm ⋮ Uncovering generalized-network structure in matrices ⋮ Nonseparating Cocircuits in Binary Matroids ⋮ Distance realization problems with applications to internet tomography