@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-hal-00077489v1> a dcat:Dataset ;
    dct:description """
              Classes of graphs with bounded expansion generalize both proper minor closed classes and classes with bounded degree. For any class with bounded expansion C and any integer p there exists a constant N( C,p) so that the vertex set of any graph G∈C may be partitioned into at most N(C,p) parts, any i≤ p parts of them induce a subgraph of tree-width at most (i-1) (actually, of tree-depth at most i, what is sensibly stronger). Such partitions are central to the resolution of homomorphism problems like restricted homomorphism dualities. We give here a simple algorithm to compute such partitions and prove that if we restrict the input graph to some fixed class C with bounded expansion, the running time of the algorithm is bounded by a linear function of the order of the graph (for fixed C and p). This result is applied to get a linear time algorithm for the subgraph isomorphism problem with fixed pattern and input graphs in a fixed class with bounded expansion. More generally, let φ be a first order logic sentence. We prove that any fixed graph property of type ``∃ X: (|X|≤ p) /\\ (G[X]⊧φ)'' may be decided in linear time for input graphs in a fixed class with bounded expansion.
            """ ;
    dct:identifier "hal-00077489" ;
    dct:issued "2026-05-15T08:31:27.126677"^^xsd:dateTime ;
    dct:language "en" ;
    dct:modified "2026-05-15T08:31:27.126682"^^xsd:dateTime ;
    dct:publisher <https://rec.harvest-normandie.data4citizen.com/organization/cce9db95-46d9-4dc2-84b6-764215d0a002> ;
    dct:title "Linear time low tree-width partitions and algorithmic consequences" ;
    dcat:contactPoint [ a vcard:Organization ;
            vcard:fn "CCSD" ] ;
    dcat:distribution <https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00077489v1/resource/86137499-d0d1-4c13-848d-cd670e6627a5> ;
    dcat:keyword "conference-papers",
        "infoeu-reposemanticsconferenceobject",
        "mathmath-comathematics-mathcombinatorics-mathco" ;
    dcat:landingPage <STOC%2706.%20Proceedings%20of%20the%2038th%20Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing> .

<STOC%2706.%20Proceedings%20of%20the%2038th%20Annual%20ACM%20Symposium%20on%20Theory%20of%20Computing> a foaf:Document .

<https://rec.harvest-normandie.data4citizen.com/dataset/oai-hal-hal-00077489v1/resource/86137499-d0d1-4c13-848d-cd670e6627a5> a dcat:Distribution ;
    dct:format "HTML" ;
    dct:issued "2026-05-15T08:31:27.129971"^^xsd:dateTime ;
    dct:modified "2026-05-15T08:31:27.117937"^^xsd:dateTime ;
    dct:title "Linear time low tree-width partitions and algorithmic consequences" ;
    dcat:accessURL <https://hal.science/hal-00077489> .

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