Name
Abstract | ||
|---|---|---|
Graph complexity measures like tree-width, clique-width, NLC-width and rank-width are important because they yield Fixed Parameter Tractable algorithms. Rank-width is based on ranks of adjacency matrices of graphs over GF(2). We propose here algebraic operations on graphs that characterize rank-width. For algorithmic purposes, it is important to represent graphs by balanced terms. We give a unique theorem that generalizes several "balancing theorems" for tree-width and clique-width. New results are obtained for rank-width and a variant of clique-width, called m-clique-width. |
Year | DOI | Venue |
|---|---|---|
2007 | 10.1007/978-3-540-74839-7_7 | WG |
Keywords | Field | DocType |
balanced term,parameter tractable algorithm,balanced graph expression,new result,algebraic operation,algorithmic purpose,graph operation,graph complexity measure,unique theorem,adjacency matrix,uniqueness theorem | Graph operations,Discrete mathematics,Indifference graph,Combinatorics,Modular decomposition,Comparability graph,Line graph,Chordal graph,Graph product,Pathwidth,Mathematics | Conference |
Volume | ISSN | ISBN |
4769 | 0302-9743 | 3-540-74838-5 |
Citations | PageRank | References |
12 | 0.63 | 14 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Bruno Courcelle | 1 | 3418 | 388.00 |
| Mamadou Moustapha Kanté | 2 | 172 | 20.93 |