An Almost Linear-Time Algorithm for Graph Realization

DOI10.1287/moor.13.1.99zbMath0654.05023MaRDI 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

tree; algorithm; network structure; planarity testing; graph-realization problem

Mathematics Subject Classification ID

05C05: Trees

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

Related Items

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, Exact algorithms and applications for tree-like Weighted Set Cover, The structure of bases in bicircular matroids, On the complexity of recognizing directed path families, Integrality properties of edge path tree families, Vertex covering by paths on trees with its applications in machine translation, Decomposition and optimization over cycles in binary matroids, Layering strategies for creating exploitable structure in linear and integer programs, Recognizing hidden bicircular networks, A heuristic for finding embedded network structure in mathematical programmes, On testing consecutive-ones property in parallel, Computational implementation of Fujishige's graph realizability algorithm, Uncovering generalized-network structure in matrices, Distance realization problems with applications to internet tomography, Future paths for integer programming and links to artificial intelligence, The arborescence-realization problem, Independence and port oracles for matroids, with an application to computational learning theory, Recognizing binet matrices