Abstrakt. Vi anser ekonomiska representationer för sökvägen information i en riktad graf. En riktad graf G sägs vara en transitiv minskning av den riktade grafen G förutsatt att (i) G har en riktad väg från vertex u till vertex v om och endast om G har en riktad väg från vertex u till vertex v, och (ii) det inte finns någon graf med färre bågar än G uppfyller villkor (i). Även om riktade grafer med cykler kan ha mer än en sådan representation, väljer vi en naturlig kanonisk representant som den transitiva reduktionen för sådana grafer. Det visas att tids komplexiteten hos den bästa algoritmen för att hitta den transitiva minskningen av en graf är samma som tiden att beräkna den transitiva stängningen av en graf eller utföra Boolesk matris multiplikation.
Detta problem är relaterat till en standard beräkningsproblem, konstruktionen av den transitiva minskningen av en riktad acyklisk graf eller motsvarande täckande graf av en delvis beställd uppsättning REF.
The Transitive Reduction of a Directed Graph
{'venue': 'SIAM J. Comput.', 'journal': 'SIAM J. Comput.', 'mag_field_of_study': ['Mathematics', 'Computer Science']}