Abstract-Den berömda max-flöde min-cut teorem anger att en källa nod kan skicka information genom ett nätverk ( ) till en diskbänk nod med en hastighet som bestäms av min-cut separation och. Nyligen har det visat sig att denna hastighet också kan uppnås för multicasting till flera sänkor, förutsatt att de mellanliggande noderna tillåts att koda om den information de får. Vi visar exempel på nätverk där de möjliga satser som erhålls genom kodning vid mellanliggande noder är godtyckligt större än om kodning inte är tillåten. Vi ger deterministiska polynomalgoritmer och ännu snabbare randomiserade algoritmer för att utforma linjära koder för riktade acykliska grafer med kanter av enhetens kapacitet. Vi utökar dessa algoritmer till heltal kapacitet och till koder som är toleranta mot kantfel.
Det har också visat sig att sådana skalära linjära koder kan utformas effektivt REF.
Polynomial time algorithms for multicast network code construction
{'venue': 'IEEE Transactions on Information Theory', 'journal': 'IEEE Transactions on Information Theory', 'mag_field_of_study': ['Computer Science']}