Applications of the Frobenius number

J. L. Ramírez Alfonsín

in The Diophantine Frobenius Problem

Published in print December 2005 | ISBN: 9780198568209
Published online September 2007 | e-ISBN: 9780191718229 | DOI:

Series: Oxford Lecture Series in Mathematics and Its Applications

 Applications of the Frobenius number

Show Summary Details


This chapter presents a number of applications of FP to a variety of problems. The complexity analysis of the Shellsort method was not well understood until J. Incerpi and R. Sedgewick nicely observed that FP can be used to obtain upper bounds for the running time of this fundamental sorting algorithm. This chapter starts by explaining this application. It then explains how FP may be applied to analyse Petri nets, to study partitions of vector spaces, to compute exact resolutions via Rødseth's method for finding the Frobenius number when n = 3, to investigate Algebraic Geometric codes via the properties of special semigroups and their corresponding conductors, and to study tiling problems. The chapter also discusses three applications of the denumerant. An application of the modular change problem to study nonhypohamiltonian graphs, and of the vector generalization to give a new method for generating random vectors are presented.

Keywords: Shellsort method; Petri nets; tilings; monomial Curves; denumerant; nonhypohamitonian graphs; vectors

Chapter.  10973 words.  Illustrated.

Subjects: Algebra

Full text: subscription required

How to subscribe Recommend to my Librarian

Buy this work at Oxford University Press »

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content. subscribe or purchase to access all content.