Some notes on bounded starwidth graphs

被引：2

作者：

van Ee, Martijn ^{[1
]}

机构：

[1] Vrije Univ Amsterdam, De Boelelaan 1105, NL-1081 HV Amsterdam, Netherlands

来源：

INFORMATION PROCESSING LETTERS | 2017年 / 125卷

关键词：

Starwidth; Graph parameter; Graph minor; FPT; Computational complexity; COMPLEXITY;

D O I：

10.1016/j.ipl.2017.04.011

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We introduce the graph parameter starwidth. We show results on characterization, complexity and the relation with other parameters. We also discuss the complexity of problems on bounded starwidth graphs. (C) 2017 Elsevier B.V. All rights reserved.

引用

页码：9 / 14

页数：6

共 12 条

[1]

Blum A., 1994, Proceedings of the Twenty-Sixth Annual ACM Symposium on the Theory of Computing, P163, DOI 10.1145/195058.195125

[2]

Bodlaender H. L., 1993, Acta Cybernetica, V11, P1

[3] THE MONADIC 2ND-ORDER LOGIC OF GRAPHS .1. RECOGNIZABLE SETS OF FINITE GRAPHS [J].

COURCELLE, B .

INFORMATION AND COMPUTATION, 1990, 85 (01) :12-75

[4]

Downey R.G., 1999, MG COMP SCI

[5] THE COMPLEXITY OF HARMONIOUS COLORING FOR TREES [J].

EDWARDS, K ;

MCDIARMID, C .

DISCRETE APPLIED MATHEMATICS, 1995, 57 (2-3) :133-144

[6]

Karp R.M., 1975, COMPLEXITY COMPUTER, P85, DOI DOI 10.1007/978-3-540-68279-08

[7] Motif search in graphs: Application to metabolic networks [J].

Lacroix, Vincent ;

Fernandes, Cristina G. ;

Sagot, Marie-France .

IEEE-ACM TRANSACTIONS ON COMPUTATIONAL BIOLOGY AND BIOINFORMATICS, 2006, 3 (04) :360-368

[8] Tree-depth, subgraph coloring and homomorphism bounds [J].

Nesetril, Jaroslav ;

Ossona de Mendez, Patrice .

EUROPEAN JOURNAL OF COMBINATORICS, 2006, 27 (06) :1022-1041

[9] ON THE COMPLEXITY OF EDGE LABELINGS FOR TREES [J].

PERL, Y ;

ZAKS, S .

THEORETICAL COMPUTER SCIENCE, 1982, 19 (01) :1-16

[10] GRAPH MINERS .13. THE DISJOINT PATHS PROBLEM [J].

ROBERTSON, N ;

SEYMOUR, PD .

JOURNAL OF COMBINATORIAL THEORY SERIES B, 1995, 63 (01) :65-110

← 1 2 →