Preliminary versionA preliminary version of these results was presented in: Rolf H. Möhring, Matthias Müller-Hannemann, and Karsten Weihe. Using network flows for surface modeling. In Proceedings of the Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 350-359, San Francisco, California, 22-24 January 1995.
Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Nonnumerical Algorithms and Problems -- computations on discrete structures; G.2.2 [Discrete Mathematics]: Graph Theory -- graph algorithms, network problems; J.6 [Computer-Aided Engineering]
General Terms: Algorithms, design, experimentation
Additional Key Words and Phrases: Augmenting paths, $b$-matching problem, bidirected flows, mesh generation, $\mathcal{NP}$-completeness, templates
Selected references
- Richard P. Anstee. A polynomial algorithm for b-matchings: an alternative approach. Information Processing Letters, 24(3):153-157, 13 February 1987.
- Kurt Mehlhorn and Stefan Nä}her. LEDA: A platform for combinatorial and geometric computing. Communications of the ACM, 38(1):96-102, January 1995.