Cellular bipartite graphs

被引：19

作者：

Bandelt, HJ ^{[1
]}

Chepoi, V ^{[1
]}

机构：

[1] UNIV HAMBURG,MATH SEMINAR,D-20146 HAMBURG,GERMANY

来源：

EUROPEAN JOURNAL OF COMBINATORICS | 1996年 / 17卷 / 2-3期

关键词：

D O I：

10.1006/eujc.1996.0011

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

In this paper we investigate the graphs that are obtained from single edges and even cycles by successive gated amalgamations. These 'cellular' graphs are characterized among bipartite graphs by having a totally decomposable shortest-path metric, and can be recognized by a quadratic time algorithm. (C) 1996 Academic Press Limited

引用

收藏

页码：121 / 134

页数：14

相关论文

共 14 条

[1] Split Decomposition: A New and Useful Approach to Phylogenetic Analysis of Distance Data [J].

Bandelt, Hans-Juergen ;

Dress, Andreas W. M. .

MOLECULAR PHYLOGENETICS AND EVOLUTION, 1992, 1 (03) :242-252

[2] MEDIANS IN MEDIAN GRAPHS [J].

BANDELT, HJ ;

BARTHELEMY, JP .

DISCRETE APPLIED MATHEMATICS, 1984, 8 (02) :131-142

[3] QUASI-MEDIAN GRAPHS AND ALGEBRAS [J].

BANDELT, HJ ;

MULDER, HM ;

WILKEIT, E .

JOURNAL OF GRAPH THEORY, 1994, 18 (07) :681-703

[4] PSEUDO-MEDIAN GRAPHS - DECOMPOSITION VIA AMALGAMATION AND CARTESIAN MULTIPLICATION [J].

BANDELT, HJ ;

MULDER, HM .

DISCRETE MATHEMATICS, 1991, 94 (03) :161-180

[5] HEREDITARY MODULAR GRAPHS [J].

BANDELT, HJ .

COMBINATORICA, 1988, 8 (02) :149-157

[6] A CANONICAL DECOMPOSITION-THEORY FOR METRICS ON A FINITE-SET [J].

BANDELT, HJ ;

DRESS, AWM .

ADVANCES IN MATHEMATICS, 1992, 92 (01) :47-105

[7] GRAPHS WITH INTRINSIC S3 CONVEXITIES [J].

BANDELT, HJ .

JOURNAL OF GRAPH THEORY, 1989, 13 (02) :215-228

[8]

Chepoi V., 1986, MODELIROVANIE INFORM, P88

[9] L1-RIGID GRAPHS [J].

DEZA, M ;

LAURENT, M .

JOURNAL OF ALGEBRAIC COMBINATORICS, 1994, 3 (02) :153-175

[10]

DEZA M, IN PRESS J COMP APPL