检索结果-内蒙古大学图书馆

Multiple hypernode hitting sets and smallest two-cores with targets

JOURNAL OF COMBINATORIAL OPTIMIZATION 2009年第3期18卷 294-306页

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden

The multiple weighted hitting set problem is to find a subset of nodes in a hypergraph that hits every hyperedge in at least m nodes. We extend the problem to a notion of hypergraphs with so-called hypernodes and show that, for m=2, it remains fixed-parameter tractable (FPT), parameterized by the number of hyperedges. This is accomplished by a nontrivial extension of the dynamic programming algorithm for hypergraphs. The algorithm might be interesting for certain assignment problems, but here we need it as a tool to solve another problem motivated by network analysis: A d-core of a graph is a subgraph in which every vertex has at least d neighbors. We give an FPT algorithm that computes a smallest 2-core including a given set of target vertices, where the number of targets is the parameter. This FPT result is best possible in the sense that no FPT algorithm for 3-cores can be expected.

关键词： Hitting set Job assignment Parameterized algorithms dynamic programming on subsets Cores in graphs

来源：评论

学校读者我要写书评

暂无评论

On an Ordering Problem in Weighted Hypergraphs 32nd

On an Ordering Problem in Weighted Hypergraphs

引用

32nd International Workshop on Combinatorial Algorithms (IWOCA)

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden Fraunhofer Chalmers Res Ctr Ind Math Gothenburg Sweden

ISBN: (纸本)9783030799878;9783030799861

We consider the problem of mapping the n vertices of an edge-weighted hypergraph to the points 1, ... , n on the real line, so as to minimize the weighted sum of the coordinates of right ends of all edges. This problem naturally appears in warehouse logistics: n shelves are arranged in one row, every shelf can host one type of items, the edges are sets of items requested together, their weights are the request frequencies, and items must be picked from the shelves and brought to a collection point at the left end of the row. The problem is to place all items so as to minimize the average length of the collection tours. It is NP-complete even for graphs, but it can be solved in O*(2(n)) time by dynamic programming on subsets. In the present work we focus on hypergraphs with small connected components, which also has a practical motivation: Typical requests comprise related items from only one of many small disjoint groups. As a first result we solve, in polynomial time, an auxiliary problem with prescribed ordering in every component. For the unrestricted problem we conclude some worst-case time bounds that beat O* (2(n)) for components of sizes up to 6. Some simple preprocessing can further reduce the time in many instances. Furthermore, the case of star graphs can be solved via bipartite matchings. Finally, there remain various interesting open problems.

关键词： Hypergraph linear arrangement dynamic programming on subsets Convex hull Bipartite matching Warehouse logistics

来源：评论

学校读者我要写书评

暂无评论

Ordering a Sparse Graph to Minimize the Sum of Right Ends of Edges 31st

Ordering a Sparse Graph to Minimize the Sum of Right Ends of...

引用

31st International Workshop on Combinatorial Algorithms (IWOCA)

作者： Damaschke, Peter Chalmers Univ Dept Comp Sci & Engn S-41296 Gothenburg Sweden Fraunhofer Chalmers Res Ctr Ind Math S-41288 Gothenburg Sweden

ISBN: (纸本)9783030489656;9783030489663

Motivated by a warehouse logistics problem we study mappings of the vertices of a graph onto prescribed points on the real line that minimize the sum (or equivalently, the average) of the coordinates of the right ends of all edges. We focus on graphs whose edge numbers do not exceed the vertex numbers too much, that is, graphs with few cycles. Intuitively, dense subgraphs should be placed early in the ordering, in order to finish many edges soon. However, our main "calculation trick" is to compare the objective function with the case when (almost) every vertex is the right end of exactly one edge. The deviations from this case are described by "charges" that can form "dipoles". This reformulation enables us to derive polynomial algorithms and NP-completeness results for relevant special cases, and FPT results.

关键词： Minimum linear arrangement Pick-by-order Cycle Tree dynamic programming on subsets Elimination ordering 2-core 3-core

来源：评论

学校读者我要写书评

暂无评论

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

建议与咨询 留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案： 新增检索档案 确定 取消

请选择收藏分类： 新增自定义分类 确定 取消

通借通还

建议与咨询留下您的常用邮箱和电话号码，以便我们向您反馈解决方案和替代方法

请选择保存的检索档案：

请选择收藏分类：