This paper presents polynomial time algorithms for constructing linear multicast network codes that achieve the maximum possible data rate for multicasting to multiple sinks. The authors demonstrate that allowing intermediate nodes to re-encode information can significantly increase the achievable rate compared to simple routing. They provide deterministic and randomized algorithms for designing linear codes on directed acyclic graphs with unit capacity edges, and extend these algorithms to handle integer capacities and codes that are robust to edge failures. The paper begins by introducing the problem of multicasting in directed acyclic graphs, where the goal is to send the same information from a source to multiple sinks at maximum data rate. It shows that without coding, the achievable rate is limited by the minimum cut between the source and any sink, but with coding, this rate can be achieved. The authors then describe a polynomial time algorithm for constructing linear codes that achieve this maximum rate, using a combination of flow algorithms and linear algebra techniques. The algorithm works in two stages: first, it finds edge-disjoint paths from the source to each sink, and then it designs linear coding for each edge to ensure that all sinks can reconstruct the original information. The algorithm maintains an invariant that ensures the linear independence of the coding vectors, allowing for efficient decoding at each sink. The paper also discusses the extension of these algorithms to handle integer capacities and robust codes that can tolerate edge failures. It shows that with a sufficiently large finite field, the algorithms can be implemented in polynomial time, and that the resulting codes can achieve the maximum possible data rate even in the presence of edge failures. The authors conclude that their algorithms provide a practical and efficient way to design linear multicast network codes that achieve the maximum possible data rate, and that these codes are robust to edge failures. The results have important implications for the design of efficient and reliable communication networks.This paper presents polynomial time algorithms for constructing linear multicast network codes that achieve the maximum possible data rate for multicasting to multiple sinks. The authors demonstrate that allowing intermediate nodes to re-encode information can significantly increase the achievable rate compared to simple routing. They provide deterministic and randomized algorithms for designing linear codes on directed acyclic graphs with unit capacity edges, and extend these algorithms to handle integer capacities and codes that are robust to edge failures. The paper begins by introducing the problem of multicasting in directed acyclic graphs, where the goal is to send the same information from a source to multiple sinks at maximum data rate. It shows that without coding, the achievable rate is limited by the minimum cut between the source and any sink, but with coding, this rate can be achieved. The authors then describe a polynomial time algorithm for constructing linear codes that achieve this maximum rate, using a combination of flow algorithms and linear algebra techniques. The algorithm works in two stages: first, it finds edge-disjoint paths from the source to each sink, and then it designs linear coding for each edge to ensure that all sinks can reconstruct the original information. The algorithm maintains an invariant that ensures the linear independence of the coding vectors, allowing for efficient decoding at each sink. The paper also discusses the extension of these algorithms to handle integer capacities and robust codes that can tolerate edge failures. It shows that with a sufficiently large finite field, the algorithms can be implemented in polynomial time, and that the resulting codes can achieve the maximum possible data rate even in the presence of edge failures. The authors conclude that their algorithms provide a practical and efficient way to design linear multicast network codes that achieve the maximum possible data rate, and that these codes are robust to edge failures. The results have important implications for the design of efficient and reliable communication networks.