@prefix dcat: <http://www.w3.org/ns/dcat#> .
@prefix dct: <http://purl.org/dc/terms/> .
@prefix foaf: <http://xmlns.com/foaf/0.1/> .
@prefix vcard: <http://www.w3.org/2006/vcard/ns#> .
@prefix xsd: <http://www.w3.org/2001/XMLSchema#> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-tel-00804206v1> a dcat:Dataset ;
    dct:description """
              This thesis tackles NP-hard problems with combinatorial techniques, focusing on the framework of Fixed-Parameter Tractability. Themain problems considered here are MULTICUT and MAXIMUM LEAF OUT-BRANCHING. MULTICUT is a natural generalisation of the cut problem, and consists in simultaneously separating prescribed pairs of vertices by removing as few edges as possible in a graph. MAXIMUM LEAF OUT-BRANCHING consists in finding a spanning directed tree with as many leaves as possible in a directed graph. The main results of this thesis are the following. We show that MULTICUT is FPT when parameterized by the solution size, i.e. deciding the existence of a multicut of size k in a graph with n vertices can be done in time f(k) ∗ poly(n). We show that MULTICUT IN TREES admits a polynomial kernel, i.e. can be reduced to instances of size polynomial in k. We give anO∗(3.72k) algorithmforMAXIMUM LEAF OUT-BRANCHING and the first non-trivial (better than 2n) exact algorithm. We also provide a quadratic kernel and a constant factor approximation algorithm. These algorithmic results are based on combinatorial results and structural properties, involving tree decompositions,minors, reduction rules and s−t numberings, among others. We present results obtained with combinatorial techniques outside the scope of parameterized complexity: a characterization of Helly circle graphs as the diamond-free circle graphs, and a partial characterisation of 2-well-quasi-ordered classes of graphs.
            """ ;
    dct:identifier "tel-00804206" ;
    dct:issued "2026-05-12T04:38:59.535300"^^xsd:dateTime ;
    dct:language "en" ;
    dct:modified "2026-05-12T04:38:59.535306"^^xsd:dateTime ;
    dct:publisher <https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> ;
    dct:title "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." ;
    dcat:contactPoint [ a vcard:Organization ;
            vcard:fn "CCSD" ] ;
    dcat:distribution <https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-tel-00804206v1/resource/c5400139-32b3-4ae6-80d4-08b26543315f> ;
    dcat:keyword "algorithmes-dapproximation",
        "algorithmes-exponentiels",
        "algorithmes-parametres",
        "arbres-avec-beaucoup-de-feuilles",
        "bel-ordre",
        "complexite-parametree",
        "fpt",
        "graphes-de-cercle-helly",
        "infoeu-reposemanticsdoctoralthesis",
        "infoinfo-dmcomputer-science-csdiscrete-mathematics-csdm",
        "multicoupe",
        "noyaux",
        "theses" ;
    dcat:landingPage <https://theses.hal.science/tel-00804206> .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-tel-00804206v1/resource/c5400139-32b3-4ae6-80d4-08b26543315f> a dcat:Distribution ;
    dct:format "HTML" ;
    dct:issued "2026-05-12T04:38:59.554697"^^xsd:dateTime ;
    dct:modified "2026-05-12T04:38:59.516590"^^xsd:dateTime ;
    dct:title "Techniques combinatoires pour les algorithmes paramétrés et les noyaux, avec applications aux problèmes de multicoupe." ;
    dcat:accessURL <https://theses.hal.science/tel-00804206> .

<https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> a foaf:Agent ;
    foaf:name "test_moissonnage_selune" .

<https://theses.hal.science/tel-00804206> a foaf:Document .