A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs

Broersma HJ.; Kloks T.; Dahlhaus E.

首页> 外文期刊>Discrete Applied Mathematics >A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs

【24h】

A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs

机译：距离遗传图的最小填充和树宽的线性时间算法

获取原文

获取原文并翻译 | 示例

掌桥外文数据库（机构版） >>

开具论文收录证明 >>

文献代查 >>

页面导航

摘要
著录项
相似文献
相关主题

摘要

A graph is distance hereditary if it preserves distances in all its connected induced subgraphs. The MINIMUM FILL-IN problem is the problem of finding a chordal supergraph with the smallest possible number of edges. The TREEWIDTH problem is the problem of finding a chordal embedding of the graph with the smallest possible clique number. In this paper we show that both problems are solvable in linear time for distance hereditary graphs. (C) 2000 Elsevier Science B.V. All rights reserved. [References: 23]

著录项

来源
《Discrete Applied Mathematics》 |2000年第3期|共34页
作者
Broersma HJ.; Kloks T.; Dahlhaus E.;
展开▼
作者单位

展开▼
收录信息
原文格式 PDF
正文语种 eng
中图分类离散数学;
关键词
Distance hereditary graphs; Minimum fill-in; Treewidth; Chordal graphs; Linear time algorithm; Fragment tree; Tree representation; Chordal bipartite graphs; Cographs; Tree;

机译：距离遗传图;最小填充;树宽;Chordal图;线性时间算法;片段树;树表示;Chordal二分图;Cographs;树;

相似文献

外文文献
中文文献
专利

1. A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs [J] . Broersma HJ., Kloks T., Dahlhaus E. Discrete Applied Mathematics . 2000,第1a3期

机译：距离遗传图的最小填充和树宽的线性时间算法
2. EXACT ALGORITHMS FOR TREEWIDTH AND MINIMUM FILL-IN [J] . FEDOR V. FOMIN, DIETER KRATSCH, IOAN TODINCA, SIAM Journal on Computing . 2009,第3期

机译：精确的算法，适用于宽度和最小填充
3. POLYNOMIAL TIME ALGORITHMS FOR COMPUTING A MINIMUM HULL SET IN DISTANCE-HEREDITARY AND CHORDAL GRAPHS [J] . Kante Mamadou Moustapha, Nourine Lhouari SIAM Journal on Discrete Mathematics . 2016,第1期

机译：用于计算距离遗传和跨域图中的最小船体集的多项式时间算法
4. Computing Treewidth and Minimum Fill-in for Permutation Graphs in Linear Time [C] . Daniel Meister International Workshop on Graph-Theoretic Concepts in Computer Science(WG 2005); 20050623-25; Metz(FR) . 2005

机译：计算线性图中置换图的树宽和最小填充
5. Linear-time algorithms for graphs with bounded branchwidth. [D] . Christian, William Anderson, Jr. 2003

机译：具有有限分支宽度的图的线性时间算法。
6. Linear-time algorithms for phylogenetic tree completion under Robinson–Foulds distance [O] . Mukul S. Bansal 2020

机译：Robinson–Foulds距离下系统发育树完成的线性时间算法
7. A linear time algorithm for minimum fill-in and treewidth for distance heredity graphs [O] . Broersma, Haitze J., Dahlhaus, E., Kloks, A.J.J., 2000

机译：距离遗传图的最小填充和树宽的线性时间算法
8. Algorithms for the Treewidth and Minimum Fill-in of HHD-Free Graphs [R] . Broersma, H. J., Dahlhaus, E., Kloks, T. 1996

机译：无HHD图的树宽和最小填充算法

A linear time algorithm for minimum fill-in and treewidth for distance hereditary graphs

摘要

著录项

相似文献

相关主题

期刊订阅