文献类型：期刊文章

作　　者：邓冬林[1] 王海燕[2] 徐建华[3]

机构地区：[1]云南农业大学基础与信息工程学院,云南昆明650201 [2]云南财经大学统计与数学学院,云南昆明650221 [3]昆明理工大学学生社区教育管理中心,云南昆明650093

出　　处：《昆明理工大学学报（自然科学版）》

基　　金：国家自然科学基金项目(41101128)

年　　份：2014

卷　　号：39

期　　号：3

起止页码：122-128

语　　种：中文

收录情况：BDHX、BDHX2011、CAS、CSA、IC、INSPEC、RCCSE、ZGKJHX、核心刊

摘　　要：本文基于经典一维装箱问题进行深入研究.首先将装箱问题与有向图相结合,研究了无有向圈的有向图上的装箱问题以及基础圈有向图上的装箱问题,同时对这两个问题设计了相应的近似算法;其次,深化研究成果,将装箱问题同染色问题相结合,研究了无有向圈的有向图上的染色装箱问题以及基础圈有向图上的染色装箱问题,并对这两个问题分别设计了相应的近似算法和启发式算法.

关 键 词：有向图 装箱问题 染色装箱问题  FF 算法  FFD算法  NP-完备性  

分 类 号：O224]