DC Field | Value | Language |
---|---|---|
dc.contributor.author | Oum, Sang-il | ko |
dc.date.accessioned | 2013-03-06T17:07:56Z | - |
dc.date.available | 2013-03-06T17:07:56Z | - |
dc.date.created | 2012-02-06 | - |
dc.date.created | 2012-02-06 | - |
dc.date.issued | 2005-09 | - |
dc.identifier.citation | JOURNAL OF COMBINATORIAL THEORY SERIES B, v.95, no.1, pp.79 - 100 | - |
dc.identifier.issn | 0095-8956 | - |
dc.identifier.uri | http://hdl.handle.net/10203/87720 | - |
dc.description.abstract | The rank-width is a graph parameter related in terms of fixed functions to clique-width but more tractable. Clique-width has nice algorithmic properties, but no good "minor" relation is known analogous to graph minor embedding for tree-width. In this paper, we discuss the vertex-minor relation of graphs and its connection with rank-width. We prove a relationship between vertex-minors of bipartite graphs and minors of binary matroids, and as an application, we prove that bipartite graphs of sufficiently large rank-width contain certain bipartite graphs as vertex-minors. The main theorem of this paper is that for fixed k, there is a finite list of graphs such that a graph G has rank-width at most k if and only if no graph in the list is isomorphic to a vertex-minor of G. Furthermore, we prove that a graph has rank-width at most I if and only if it is distance-hereditary. (C) 2005 Elsevier Inc. All rights reserved. | - |
dc.language | English | - |
dc.publisher | ACADEMIC PRESS INC ELSEVIER SCIENCE | - |
dc.subject | GRAPH MINORS | - |
dc.subject | BRANCH-WIDTH | - |
dc.subject | PLANAR GRAPH | - |
dc.subject | CLIQUE-WIDTH | - |
dc.subject | MATROIDS | - |
dc.subject | DECOMPOSITION | - |
dc.subject | OBSTRUCTIONS | - |
dc.title | Rank-width and vertex-minors | - |
dc.type | Article | - |
dc.identifier.wosid | 000231264400006 | - |
dc.identifier.scopusid | 2-s2.0-23244468510 | - |
dc.type.rims | ART | - |
dc.citation.volume | 95 | - |
dc.citation.issue | 1 | - |
dc.citation.beginningpage | 79 | - |
dc.citation.endingpage | 100 | - |
dc.citation.publicationname | JOURNAL OF COMBINATORIAL THEORY SERIES B | - |
dc.identifier.doi | 10.1016/j.jctb.2005.03.003 | - |
dc.contributor.localauthor | Oum, Sang-il | - |
dc.type.journalArticle | Article | - |
dc.subject.keywordAuthor | clique-width | - |
dc.subject.keywordAuthor | rank-width | - |
dc.subject.keywordAuthor | vertex-minor | - |
dc.subject.keywordAuthor | local complementation | - |
dc.subject.keywordAuthor | pivoting | - |
dc.subject.keywordAuthor | branch-width | - |
dc.subject.keywordAuthor | binary matroid | - |
dc.subject.keywordPlus | GRAPH MINORS | - |
dc.subject.keywordPlus | BRANCH-WIDTH | - |
dc.subject.keywordPlus | PLANAR GRAPH | - |
dc.subject.keywordPlus | CLIQUE-WIDTH | - |
dc.subject.keywordPlus | MATROIDS | - |
dc.subject.keywordPlus | DECOMPOSITION | - |
dc.subject.keywordPlus | OBSTRUCTIONS | - |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.