DC Field | Value | Language |
---|---|---|
dc.contributor.author | Adler, Isolde | ko |
dc.contributor.author | Kanté, Mamadou Moustapha | ko |
dc.contributor.author | Kwon, O-Joung | ko |
dc.date.accessioned | 2023-10-26T03:00:22Z | - |
dc.date.available | 2023-10-26T03:00:22Z | - |
dc.date.created | 2023-10-26 | - |
dc.date.issued | 2014-06 | - |
dc.identifier.citation | 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, pp.42 - 55 | - |
dc.identifier.issn | 0302-9743 | - |
dc.identifier.uri | http://hdl.handle.net/10203/313803 | - |
dc.description.abstract | We present a characterization of the linear rank-width of distance-hereditary graphs. Using the characterization, we show that the linear rank-width of every n-vertex distance-hereditary graph can be computed in time O(n2 · log(n)), and a linear layout witnessing the linear rank-width can be computed with the same time complexity. For our characterization, we combine modifications of canonical split decompositions with an idea of [Megiddo, Hakimi, Garey, Johnson, Papadimitriou: The complexity of searching a graph. JACM1988], used for computing the path-width of trees. We also provide a set of distance-hereditary graphs which contains the set of distance-hereditary vertex-minor obstructions for linear rank-width. The set given in [Jeong, Kwon, Oum: Excluded vertex-minors for graphs of linear rank-width at most k. STACS 2013: 221–232] is a subset of our obstruction set. | - |
dc.language | English | - |
dc.publisher | Springer Verlag | - |
dc.title | Linear rank-width of distance-hereditary graphs | - |
dc.type | Conference | - |
dc.identifier.wosid | 000371248200004 | - |
dc.identifier.scopusid | 2-s2.0-84909588121 | - |
dc.type.rims | CONF | - |
dc.citation.beginningpage | 42 | - |
dc.citation.endingpage | 55 | - |
dc.citation.publicationname | 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 | - |
dc.identifier.conferencecountry | FR | - |
dc.identifier.conferencelocation | Nouan le Fuzelier | - |
dc.identifier.doi | 10.1007/978-3-319-12340-0_4 | - |
dc.contributor.nonIdAuthor | Adler, Isolde | - |
dc.contributor.nonIdAuthor | Kanté, Mamadou Moustapha | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.