图的最小控制树问题

林浩, 林澜

doi:10.13371/j.cnki.chin.q.j.m.2014.01.001

数学季刊 >

2014 , Vol. 29 >Issue 1: 1 - 8

DOI: https://doi.org/10.13371/j.cnki.chin.q.j.m.2014.01.001

图的最小控制树问题

展开

1. School of Science, Henan University of Technology 2. School of Electronics and Information Engineering, Tongji University

LIN Hao (1974-), male, native of Taishan, Guangdong, an associate professor of Henan University of Technology, M.S.D., engages in network optimization.

收稿日期: 2013-03-01

网络出版日期: 2022-11-28

基金资助

Supported by NNSF of China (11101383,61373106)

收起

Minimum Dominating Tree Problem for Graphs

Expand

1. School of Science, Henan University of Technology 2. School of Electronics and Information Engineering, Tongji University

LIN Hao (1974-), male, native of Taishan, Guangdong, an associate professor of Henan University of Technology, M.S.D., engages in network optimization.

Received date: 2013-03-01

Online published: 2022-11-28

Supported by

Supported by NNSF of China (11101383,61373106)

Fold

摘要

A dominating tree T of a graph G is a subtree of G which contains at least one neighbor of each vertex of G.The minimum dominating tree problem is to find a dominating tree of G with minimum number of vertices,which is an NP-hard problem.This paper studies some polynomially solvable cases,including interval graphs,Halin graphs,special outer-planar graphs and others.

关键词： network optimization; minimum dominating tree; special graphs; exact evaluation

本文引用格式

林浩, 林澜 . 图的最小控制树问题[J]. 数学季刊, 2014 , 29(1) : 1 -8 . DOI: 10.13371/j.cnki.chin.q.j.m.2014.01.001

Abstract

Key words： network optimization; minimum dominating tree; special graphs; exact evaluation

Options

文章导航

模态框（Modal）标题

摘要

本文引用格式

Abstract