untitled
<OAI-PMH schemaLocation=http://www.openarchives.org/OAI/2.0/ http://www.openarchives.org/OAI/2.0/OAI-PMH.xsd>
<responseDate>2018-01-15T18:24:36Z</responseDate>
<request identifier=oai:HAL:hal-01282715v1 verb=GetRecord metadataPrefix=oai_dc>http://api.archives-ouvertes.fr/oai/hal/</request>
<GetRecord>
<record>
<header>
<identifier>oai:HAL:hal-01282715v1</identifier>
<datestamp>2018-01-11</datestamp>
<setSpec>type:UNDEFINED</setSpec>
<setSpec>subject:info</setSpec>
<setSpec>collection:CNRS</setSpec>
<setSpec>collection:UNIV-AG</setSpec>
<setSpec>collection:UNICE</setSpec>
<setSpec>collection:UNIV-PARIS7</setSpec>
<setSpec>collection:UPMC</setSpec>
<setSpec>collection:EVOLUTION_PARIS_SEINE</setSpec>
<setSpec>collection:INRIA</setSpec>
<setSpec>collection:MNHN</setSpec>
<setSpec>collection:USPC</setSpec>
<setSpec>collection:TESTANNE</setSpec>
<setSpec>collection:UPMC_POLE_4</setSpec>
<setSpec>collection:UCA-TEST</setSpec>
<setSpec>collection:IBPS</setSpec>
<setSpec>collection:UNIV-COTEDAZUR</setSpec>
</header>
<metadata><dc>
<publisher>HAL CCSD</publisher>
<title lang=en>Read networks and k-laminar graphs</title>
<creator>Völkel, Finn</creator>
<creator>Bapteste, Eric</creator>
<creator>Habib, Michel</creator>
<creator>Lopez, Philippe</creator>
<creator>Vigliotti, Chloe</creator>
<contributor>Institut de Recherche en Informatique Fondamentale (IRIF) ; Université Paris Diderot - Paris 7 (UPD7) - Centre National de la Recherche Scientifique (CNRS)</contributor>
<contributor>Evolution Paris Seine ; Université des Antilles et de la Guyane (UAG) - Université Pierre et Marie Curie - Paris 6 (UPMC) - Université Nice Sophia Antipolis (UNS) ; Université Côte d'Azur (UCA) - Université Côte d'Azur (UCA) - Centre National de la Recherche Scientifique (CNRS)</contributor>
<contributor>Networks, Graphs and Algorithms (GANG) ; Institut de Recherche en Informatique Fondamentale (IRIF) ; Université Paris Diderot - Paris 7 (UPD7) - Centre National de la Recherche Scientifique (CNRS) - Université Paris Diderot - Paris 7 (UPD7) - Centre National de la Recherche Scientifique (CNRS) - Inria de Paris ; Institut National de Recherche en Informatique et en Automatique (Inria) - Institut National de Recherche en Informatique et en Automatique (Inria)</contributor>
<contributor>Mécanismes adaptatifs : des organismes aux communautés (MECADEV) ; Centre National de la Recherche Scientifique (CNRS) - Muséum National d'Histoire Naturelle (MNHN)</contributor>
<identifier>hal-01282715</identifier>
<identifier>https://hal.inria.fr/hal-01282715</identifier>
<source>https://hal.inria.fr/hal-01282715</source>
<source>2016</source>
<identifier>ARXIV : 1603.01179</identifier>
<relation>info:eu-repo/semantics/altIdentifier/arxiv/1603.01179</relation>
<language>en</language>
<subject>[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]</subject>
<subject>[INFO] Computer Science [cs]</subject>
<type>info:eu-repo/semantics/preprint</type>
<type>Preprints, Working Papers, ...</type>
<description lang=en>In this paper we introduce k-laminar graphs a new class of graphs which extends the idea of Asteroidal triple free graphs. Indeed a graph is k-laminar if it admits a diametral path that is k-dominating. This bio-inspired class of graphs was motivated by a biological application dealing with sequence similarity networks of reads (called hereafter read networks for short). We briefly develop the context of the biological application in which this graph class appeared and then we consider the relationships of this new graph class among known graph classes and then we study its recognition problem. For the recognition of k-laminar graphs, we develop polynomial algorithms when k is fixed. For k=1, our algorithm improves a Deogun and Krastch's algorithm (1999). We finish by an NP-completeness result when k is unbounded.</description>
<date>2016-03-04</date>
</dc>
</metadata>
</record>
</GetRecord>
</OAI-PMH>
