Vi presenterar en formalisering av klassiska algoritmer för beräkning av maximalt flöde i ett nätverk: Edmonds-Karp algoritmen och push-relabel algoritmen. Vi bevisar att dessa algoritmer är korrekta och tidskomplicerade. Vårt formella bevis följer noga en standard lärobok bevis, och är tillgänglig även utan att vara en expert i Isabelle/HOL-den interaktiva teorem bevis som används för formaliseringen. Med hjälp av stegvisa förfiningsmetoder inställer vi den generiska Ford-Fulkerson-algoritmen till Edmonds-Karp-algoritm, och den generiska push-relabel-algoritmen för Goldberg och Tarjan till både ommärkning-till-front och FIFO push-relabel-algoritm. Ytterligare förfining ger sedan verifierade effektiva implementeringar av algoritmerna, som väl kan jämföras med okontrollerade referensimplementeringar.
REF utvidgade detta ytterligare och presenterade kontroller av korrektheten och tids komplexiteten hos Edmonds-Karp och push-relabel algoritmer.
Formalizing Network Flow Algorithms: A Refinement Approach in Isabelle/HOL
{'venue': 'Journal of Automated Reasoning', 'journal': 'Journal of Automated Reasoning', 'mag_field_of_study': ['Mathematics', 'Computer Science']}