Jump to ContentJump to Main Navigation
The Diophantine Frobenius Problem$
Users without a subscription are not able to see the full content.

Jorge L. Ramírez Alfonsín

Print publication date: 2005

Print ISBN-13: 9780198568209

Published to Oxford Scholarship Online: September 2007

DOI: 10.1093/acprof:oso/9780198568209.001.0001

Show Summary Details
Page of

PRINTED FROM OXFORD SCHOLARSHIP ONLINE (oxford.universitypressscholarship.com). (c) Copyright Oxford University Press, 2020. All Rights Reserved. An individual user may print out a PDF of a single chapter of a monograph in OSO for personal use. date: 28 November 2020

Applications of the Frobenius number

Applications of the Frobenius number

(p.159) 8 Applications of the Frobenius number
The Diophantine Frobenius Problem

J. L. Ramírez Alfonsín

Oxford University Press

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

Oxford Scholarship Online requires a subscription or purchase to access the full text of books within the service. Public users can however freely search the site and view the abstracts and keywords for each book and chapter.

Please, subscribe or login to access full text content.

If you think you should have access to this title, please contact your librarian.

To troubleshoot, please check our FAQs , and if you can't find the answer there, please contact us .