Of large sparse biparite graphs (say degree 4) with N verticies, roughly speaking, which of them cause the worst case running time of the Hopcroft-Karp algorithm? What is their general structure and architecture, and why does it cause a problem?

Further, in many implementations the DFS part is implemented using recursion, eg from Wikipedia:

function DFS (v)
    if v != NIL
        for each u in Adj[v]
            if Dist[ Pair_G2[u] ] == Dist[v] + 1
                if DFS(Pair_G2[u]) == true
                    Pair_G2[u] = v
                    Pair_G1[v] = u
                    return true
        Dist[v] = ∞
        return false
    return true

What is the approximate maximum depth of the recursion in the worst case?

  • 3
    $\begingroup$ The maximum recursion depth of DFS is $n$; the DFS tree might consist of a single (Hamiltonian) path. $\endgroup$ – JeffE Aug 8 '12 at 21:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.