DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kwon, O-Joung | ko |
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2014-08-29T02:06:54Z | - |
dc.date.available | 2014-08-29T02:06:54Z | - |
dc.date.created | 2014-05-20 | - |
dc.date.created | 2014-05-20 | - |
dc.date.issued | 2014-05 | - |
dc.identifier.citation | DISCRETE APPLIED MATHEMATICS, v.168, pp.108 - 118 | - |
dc.identifier.issn | 0166-218X | - |
dc.identifier.uri | http://hdl.handle.net/10203/188969 | - |
dc.description.abstract | We prove that every graph of rank-width k is a pivot-minor of a graph of tree-width at most 2k. We also prove that graphs of rank-width at most 1, equivalently distance-hereditary graphs, are exactly vertex-minors of trees, and graphs of linear rank-width at most 1 are precisely vertex-minors of paths. In addition, we show that bipartite graphs of rank-width at most 1 are exactly pivot-minors of trees and bipartite graphs of linear rank-width at most 1 are precisely pivot-minors of paths. | - |
dc.language | English | - |
dc.publisher | ELSEVIER SCIENCE BV | - |
dc.title | Graphs of small rank-width are pivot-minors of graphs of small tree-width | - |
dc.type | Article | - |
dc.identifier.wosid | 000334485900012 | - |
dc.identifier.scopusid | 2-s2.0-84896710900 | - |
dc.type.rims | ART | - |
dc.citation.volume | 168 | - |
dc.citation.beginningpage | 108 | - |
dc.citation.endingpage | 118 | - |
dc.citation.publicationname | DISCRETE APPLIED MATHEMATICS | - |
dc.identifier.doi | 10.1016/j.dam.2013.01.007 | - |
dc.embargo.liftdate | 9999-12-31 | - |
dc.embargo.terms | 9999-12-31 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | Rank-width | - |
dc.subject.keywordAuthor | Linear rank-width | - |
dc.subject.keywordAuthor | Vertex-minor | - |
dc.subject.keywordAuthor | Pivot-minor | - |
dc.subject.keywordAuthor | Tree-width | - |
dc.subject.keywordAuthor | Path-width | - |
dc.subject.keywordAuthor | Distance-hereditary | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.