On Approximating the Maximum Simple Sharing Problem

机译：关于逼近最大简单共享问题

获取原文

获取原文并翻译 | 示例

页面导航

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

摘要

In the maximum simple sharing problem (MSS), we want to compute a set of node-disjoint simple paths in an undirected bipartite graph covering as many nodes as possible of one layer of the graph, with the constraint that all paths have both endpoints in the other layer. This is a variation of the maximum sharing problem (MS) that finds important applications in the design of molecular quantum-dot cellular automata (QCA) circuits and physical synthesis in VLSI. It also generalizes the maximum weight node-disjoint path cover problem. We show that MSS is NP-complete, present a polynomial-time 5/3-approximation algorithm, and show that it cannot be approximated with a factor better than 740/739 unless P = NP.

机译：在最大简单共享问题（MSS）中，我们希望在无向二部图中计算一组节点不相交的简单路径，该图覆盖了该图的一层中尽可能多的节点，并且所有路径都具有两个端点另一层。这是最大共享问题（MS）的变体，它在分子量子点细胞自动机（QCA）电路的设计和VLSI中的物理合成中发现了重要的应用。它还概括了最大权重节点不相交的路径覆盖问题。我们表明MSS是NP完全的，提出了多项式时间5/3近似算法，并且表明除非P = NP，否则它的近似值不能超过740/739。

著录项

来源
《Algorithms and Computation; Lecture Notes in Computer Science; 4288》|2006年|547-556|共10页
会议地点 Kolkata(IN)
作者
Danny Z. Chen; Rudolf Fleischer; Jian Li; Zhiyi Xie; Hong Zhu;
展开▼
作者单位

Department of Computer Science and Engineering, University of Notre Dame, Notre Dame, IN 46556, USA;

Department of Computer Science and Engineering, Shanghai Key Laboratory of Intelligent Information Processing, Fudan University, Shanghai, China;

展开▼
会议组织
原文格式 PDF
正文语种 eng
中图分类理论、方法;
关键词

相似文献

外文文献
中文文献
专利

1. 简单Bellman问题的有限元逼近 [J] . 邓庆平数学季刊：英文版 . 1991,第002期
2. Approximating maximum edge 2-coloring in simple graphs [J] . Chen Z.-Z., Konno S., Matsushita Y. Discrete Applied Mathematics . 2010,第17期

机译：在简单图中逼近最大边缘2色
3. Approximating maximum edge 2-coloring in simple graphs via local improvement [J] . Zhi-Zhong Chen, Ruka Tanahashi Theoretical computer science . 2009,第45期

机译：通过局部改进在简单图形中逼近最大边缘2色
4. Approximate restricted maximum likelihood and approximate prediction error variance of the Mendelian sampling effect [J] . D Boichard, LR Schaeffer, AJ Lee Genetics, selection, evolution . 1992,第4期

机译：孟德尔采样效应的近似受限最大似然和近似预测误差方差
5. Approximating Maximum Edge 2-Coloring in Simple Graphs [C] . Zhi-Zhong Chen, Sayuri Konno, Yuki Matsushita Algorithmic aspects in information and management . 2010

机译：在简单图形中逼近最大边缘2色
6. Finite Element Maximum Entropy Method for Approximating Absolutely Continuous Invariant Measures [D] . Upadhyay, Tulsi. 2017

机译：近似绝对连续不变测度的有限元最大熵方法
7. Approximate restricted maximum likelihood and approximate prediction error variance of the Mendelian sampling effect [O] . D Boichard, LR Schaeffer, AJ Lee 1992

机译：孟德尔采样效应的近似受限最大似然和近似预测误差方差
8. Approximating the Maximum Sharing Problem [O] . Amitabh Chaudhary, Danny Z. Chen, Rudolf Fleischer, 2013

机译：近似最大共享问题
9. Solucoes Aproximadas para o Problema de Localizacao Simples. Algorithmo SimulatedAnnealing (Approximative Solutions for the Simple Plant Location Problem. Simulated Annealing Algorithm) [R] . Leonor de Almeida Gouveia Oliveira, M. 1991

机译：solucoes aproximadas para o problema de Localizacao simples。 algorithmo simulatedannealing（简单工厂定位问题的近似解。模拟退火算法）

On Approximating the Maximum Simple Sharing Problem

摘要

著录项

相似文献

相关主题

期刊订阅