Given a simple graph (at most one edge between u-v), with no loops or parallel edges, I have to prove that max (s,t) flow is at most O(v^2 / d^2).
I understand that this is asking to prove max flow <= C* (V^2/d^2) for some positivie c. I asked my TA (teacher assistant) and he said that we’d need to prove this by contradiction
Assume for a contradiction, there’s more than one edge between some vertices x and y. The shortest path is distance ‘d’. I’m stuck after this. In other words, I need to show that the minimum cut cannot be > v^2 / d^2
Can someone tell me which is the best algorithm for minimum cost maximum flow (and easy to implement) and from where to read will be helpful . I searched online and got names of many algorithms and unable to decide which one to study .
What are some applications where irreducible control flow is required*?
I’m particularly interested in programming language features that will be tricky to efficiently compile if the compile target does not permit irreducible control flow. For example, a programming language offering GOTO will generate irreducible control flow for some programs. What other language constructs are like this? For example, is irreducible control flow required to implement resumable exceptions?
I’m also interested in application-level uses of irreducible control flow.
(*: irreducible control flow graphs (CFGs) can be converted to reducible CFGs at some cost, and also some compiler optimizations can convert reducible CFGs to irreducible CFGs, so what I mean is that the original, unoptimized CFG produced by the source code is irreducible. Less formally, I mean that the "programmer’s intent" naturally includes irreducible control flow)
- A flow network G whose edges have capacity of 1
- G’s maximum flow |F|
- A positive integer K
Delete exactly K edges so that the flow of the network is minimized.
So I was asked to develop an algorithm for this but that’s not the issue.I would like to know if my thoughts are in the right direction because the Max Flow – Min Cut Theorem is new to me.
My thoughts :
If K is greater than or equal to |F| delete ALL of the edges that cross G’s Minimum cut and if K is still greater than zero delete random edges and the new max flow is zero
If K is equal to |F| delete ALL of the edges that cross G’s Minimum cut and the new max flow is zero
If K is less than |F| delete K of the edges that cross G’s Minimum cut and the new max flow is |F|-K
Lastly the way that I understand the Max Flow/Min Cut Theorem is that the Min (Source,Sink) cut works as a "bottleneck" to the maximum flow we can push in the network,right?
I know the answer to the question, but I still can’t understand. I have the max flow and I need to determine whether there is more than one min-cut. I know that I need to run BFS from s in the residual network, and from t in the residual net work (after changing each (u,v) to (v,u)). What I can’t understand: why would I get different results? Every example I am trying shows me the same: Any vertex reachable from s (not include s) is a vertex that is reachable from t. Am I wrong? and if I’m wrong, what is the reason some other case can happen?
Can anyone help me understand why the Ford-Fulkerson algorithm does not work in the case of irrational capacities?
Assume I have a graph representing the control flow and the call graph of a given program. I also have a first and a second statement. I now want to figure out if it is possible to execute both statements (in order) within the same program execution.
Control Flow Graph: I have a graph with all the statements of the program and edges connecting the statements determining the control flow of the program intra function (i.e., within a function).
Call Graph: I also have edges connecting any function call with the start of the function control flow of the called function.
The literature I found concerning control flow covers only intra function flow analysis and the only correct approach I can come up with is a depth first (or breadth first) search starting from the first statement. This, however, hardly feels correct as it is quite cumbersome and I would expect a better solution.
The OIDC standard requires the
nonce parameter in the authentication request when using the implicit flow:
nonce REQUIRED. String value used to associate a Client session with an ID Token, and to mitigate replay attacks.
However in the hybrid flow the
nonce is not required. Yet the
id_token is directly returned in the response and also susceptible to injection or replay.
Why is the
nonce parameter not required in hybrid flow. What secures hybrid flow from injection or replay of
I came upon this implementation of the dfs in Dinic’s algorithm written in Python
def dfs(c, f, current, capacity): tmp = capacity # What's the purpose of that? # we want to get to the sink, but we want it to be a blocking flow path if current == NROW - 1: return capacity for i in range(NROW): is_next = levels[i] == levels[current] + 1 residual_capacity = c[current][i] - f[current][i] has_more_capacity = residual_capacity > 0 if is_next and has_more_capacity: min_capacity_so_far = min(tmp, residual_capacity) flow = dfs(c, f, i, min_capacity_so_far) f[current][i] += flow f[i][current] -= flow tmp -= flow # Why do we do that return capacity - tmp # Why do we return capacity - tmp
How do we know that this dfs finds a blocking path? Also, I can’t seem to understand the usage of the temp variable.
Thanks in advance!
I have been reading a lot about OAuth 2 flow recently, and I wanted to ask if this is applicable to the app that I am building, and what type of security I should be using.
- We have a native ios/android and angular SPA app.
- We build/own/control our own backend apis, and only our frontend apps can(should) communicate with these apis.
- User logs in on a form, we validate credentials on backend, and return a JWT back, which is then used for subsequent requests. Access to most apis is restricted to logged in users, other apis are open to the net to allow users to register.
I cannot see a use case here for OAuth here, however, everything I am reading seems to suggest that it is required. We will not be delegating access to third party systems, we simply only want to validate our own customers, and only allow them to access our apis via our front end apps, after they have logged.
Is the approach I have outlined which we are currently doing correct, or do I need to implement OAuth Authorization Code flow, and if so can you please explain why ?