Maximala och minimala medelcykelproblem är viktiga problem med många applikationer i prestandaanalys av synkrona och asynkrona digitala system inklusive hastighetsanalys av inbyggda system, i diskreta event-system och i grafteori. Karps algoritm är en av de snabbaste och vanligaste algoritmerna för båda dessa problem. Vi presenterar detta dokument främst inom ramen för det maximala medelcykelproblemet. Vi visar att Karps algoritm bearbetar fler noder och bågar än vad som behövs för att nd det maximala cykelmedelvärdet för en digraf. Denna iakttagelse motiverade oss att föreslå ett nytt diagram som åtgärdar denna deciency och leder till två snabbare algoritmer med olika c haracteristics. Teoretisk analys säger oss att våra algoritmer alltid går snabbare än Karps algoritm och att de är bland de snabbaste hittills. Experiment på små referensgrafer kon rm detta faktum för de flesta av graferna. Dessa algoritmer har använts för att bygga upp ett ramverk för analys av tidsbegränsningar för inbyggda system.
Som diskuteras i REF, är den maximala cykeln genomsnittliga problemet ett specialfall av den maximala vinst-till-tid förhållande problem.
Faster Maximum and Minimum Mean Cycle Algorithms for System-Performance Analysis
{'venue': 'IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems', 'journal': None, 'mag_field_of_study': ['Computer Science']}