<?xml version="1.0" encoding="UTF-8"?>
<rdf:RDF xmlns:rdf="http://www.w3.org/1999/02/22-rdf-syntax-ns#"
         xmlns:dc="http://purl.org/dc/terms/"
         xmlns:foaf="http://xmlns.com/foaf/0.1/"
         xmlns:bibo="http://purl.org/ontology/bibo/"
         xmlns:fabio="http://purl.org/spar/fabio/"
         xmlns:owl="http://www.w3.org/2002/07/owl#"
         xmlns:event="http://purl.org/NET/c4dm/event.owl#"
         xmlns:ore="http://www.openarchives.org/ore/terms/">

    <rdf:Description rdf:about="https://research-explorer.ista.ac.at/record/21720">
        <ore:isDescribedBy rdf:resource="https://research-explorer.ista.ac.at/record/21720"/>
        <dc:title>Deterministic and exact fully-dynamic minimum cut of superpolylogarithmic size in subpolynomial time</dc:title>
        <bibo:authorList rdf:parseType="Collection">
            <foaf:Person>
                <foaf:name></foaf:name>
                <foaf:surname></foaf:surname>
                <foaf:givenname></foaf:givenname>
            </foaf:Person>
            <foaf:Person>
                <foaf:name></foaf:name>
                <foaf:surname></foaf:surname>
                <foaf:givenname></foaf:givenname>
            </foaf:Person>
            <foaf:Person>
                <foaf:name></foaf:name>
                <foaf:surname></foaf:surname>
                <foaf:givenname></foaf:givenname>
            </foaf:Person>
        </bibo:authorList>
        <bibo:abstract>We present an exact fully-dynamic minimum cut algorithm that runs in 𝑛𝑜⁡(1) deterministic update time when the minimum cut size is at most 2Θ⁡(log3/4−𝑐⁡𝑛) for any 𝑐 &gt;0, improving on the previous algorithm of Jin, Sun, and Thorup (SODA 2024) whose minimum cut size limit is (log⁡𝑛)𝑜⁡(1). Combined with graph sparsification, we obtain the first (1 +𝜖)-approximate fully-dynamic minimum cut algorithm on weighted graphs, for any 𝜖 ≥2−Θ⁡(log3/4−𝑐⁡𝑛), in 𝑛𝑜⁡(1) randomized update time.
Our main technical contribution is a deterministic local minimum cut algorithm, which replaces the randomized LocalKCut procedure from El-Hayek, Henzinger, and Li (SODA 2025).</bibo:abstract>
        <bibo:volume>2026</bibo:volume>
        <bibo:startPage>613-663</bibo:startPage>
        <bibo:endPage>613-663</bibo:endPage>
        <dc:publisher>Society for Industrial and Applied Mathematics</dc:publisher>
        <bibo:doi rdf:resource="10.1137/1.9781611978971.25" />
        <ore:similarTo rdf:resource="info:doi/10.1137/1.9781611978971.25"/>
    </rdf:Description>
</rdf:RDF>
