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

exact algorithms for Finding Partial Edge-Disjoint Paths 1

24th International Computing and Combinatorics Conference (COCOON)

作者： Deng, Yunyun Guo, Longkun Huang, Peihuang Fuzhou Univ Coll Math & Comp Sci Fuzhou Fujian Peoples R China Fuzhou Univ Coll Phys & Informat Engn Fuzhou Fujian Peoples R China

ISBN: (数字)9783319947761

ISBN: (纸本)9783319947761;9783319947754

For a given graph G with non-negative integral edge length, a pair of distinct vertices s and t, and a given positive integer delta, the k partial edge-disjoint shortest path (kPESP) problem aims to compute k shortest st-paths among which there are at most d edges shared by at least two paths. In this paper, we first present an exact algorithm with a runtime O(mnlog((1+m/n)) n + delta n(2)) for kPESP with k = 2. Then observing the algorithm can not be extended for general k, we propose another algorithm with a runtime O(delta 2(k)n(k+1)) in DAGs based on graph transformation. In addition, we show the algorithm can be extended to kPESP with an extra edge congestion constraint that each edge can be shared by at most C paths for a given integer C <= k.

关键词： Partial edge-disjoint path exact algorithm Directed acyclic graph Restricted shortest path

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for multi-objective integer non-linear programming by cutting solution space 14

Exact algorithms for multi-objective integer non-linear prog...

引用

14th International Conference on Service Systems and Service Management (ICSSSM)

作者： Li, Siqi Yu, Yang Wang, Hongfeng Huang, Xihua Northeastern Univ Inst Intelligent Syst Shenyang Liaoning Peoples R China Minist Transport Transport Planning & Res Inst Shenyang Liaoning Peoples R China

ISBN: (纸本)9781509063710

Multi-objective integer non-linear programming (MINP) problems are ubiquitous in real life, however, only the epsilon-constraint method can be used to solve MINP problems. To improve the computation time of the epsilon-constraint method, we propose improved exact algorithms to obtain all the Pareto-optimal solutions for MINP. Our contribution is to cut most non-Pareto-optimal solutions by several specific Pareto-optimal solutions before performing epsilon-constraint method. Thus, the computation time can be significantly saved. The performance of these exact algorithms are evaluated by the general instances of the multi-objective assignment problem. The computational results show that the performance of the proposed exact algorithms are better than the epsilon-constraint method.

关键词： Multi-objective cutting solution space exact algorithm Pareto-optimal solution

来源：评论

学校读者我要写书评

暂无评论

Improved parameterized and exact algorithms for cut problems on trees

引用

THEORETICAL COMPUTER SCIENCE 2015年第Part3期607卷 455-470页

作者： Kanj, Iyad Lin, Guohui Liu, Tian Tong, Weitian Xia, Ge Xu, Jinhui Yang, Boting Zhang, Fenghui Zhang, Peng Zhu, Binhai Depaul Univ Sch Comp Chicago IL 60604 USA Univ Alberta Dept Comp Sci Edmonton AB T6G 2E8 Canada Peking Univ Sch Elect Engn & Comp Sci Key Lab High Confidence Software Technol Minist EducInst Software Beijing 100871 Peoples R China Lafayette Coll Dept Comp Sci Easton PA 18042 USA SUNY Buffalo Dept Comp Sci & Engn Buffalo NY 14260 USA Univ Regina Dept Comp Sci Regina SK S4S 0A2 Canada Google Kirkland Kirkland WA 98033 USA Shandong Univ Sch Comp Sci & Technol Jinan Peoples R China Montana State Univ Dept Comp Sci Bozeman MT 59717 USA

We study the MULTICUT ON TREES and the GENERALIZED MULTIWAY CUT ON TREES problems. For the MULTICUT ON TREES problem, we present a parameterized algorithm that runs in time O*(rho(k)), where rho = root root 2 + 1 < 1.554 is the positive root of the polynomial x(4) - 2x(2) - 1. This improves the current-best algorithm of Chen et al. that runs in time O*(1.619(k)). For the GENERALIZED MULTIWAY CUT ON TREES problem, we show that this problem is solvable in polynomial time if the number of terminal sets is fixed;this answers an open question posed in a recent paper by Liu and Zhang. By reducing the GENERALIZED MULTIWAY CUT ON TREES problem to the MULTICUT ON TREES problem, our results give a parameterized algorithm that solves the GENERALIZED MULTIWAY CUT ON TREES problem in time O*(rho(k)). (C) 2015 Elsevier B.V. All rights reserved.

关键词： Multicut Multiway cut Tree Parameterized algorithm exact algorithm

来源：评论

学校读者我要写书评

暂无评论

exact algorithms for the rectilinear block packing problem

Exact algorithms for the rectilinear block packing problem

引用

International Symposium on Scheduling (ISS)

作者： Matsushita, Ken Hu, Yannan Hashimoto, Hideki Imahori, Shinji Yagiura, Mutsunori Nagoya Univ Grad Sch Informat Dept Math Informat Chikusa Ku Furo Cho Nagoya Aichi 4648601 Japan Tokyo Univ Marine Sci & Technol Dept Logist & Informat Engn Koto Ku 2-1-6 Etchujima Tokyo 1358533 Japan Chuo Univ Dept Informat & Syst Engn Bunkyo Ku 1-13-27 Kasuga Tokyo 1128551 Japan

The rectilinear block packing problem is a problem of packing a set of rectilinear blocks into a larger rectangular container with fixed width and unrestricted height. A rectilinear block is a polygonal block whose interior angles are either 90 degrees or 270 degrees. The objective is to pack all the blocks into the container so as to minimize the height of the container. This problem is among classical combinatorial optimization problems and is known to be NP-hard. In this paper, we propose two exact algorithms for the rectilinear block packing problem: one is based on two IP problems and the other is based on a new solution representation. The basic idea of our algorithms is that we iteratively compute lower and upper bounds on the optimal value until the lower bound on the value of an optimal solution for the current search space becomes larger than or equal to the best upper bound found during the search by then, or the search space becomes empty, which means that an optimal solution of this problem has been found. The computational results show that both algorithms obtain five exact and one heuristic solutions for six instances. The algorithm based on a new solution representation improves the running time of the algorithm based on two IP problems.

关键词： Strip packing Rectilinear blocks Solution representation Branch and bound exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Dijkstra meets Steiner: a fast exact goal-oriented Steiner tree algorithm

引用

MATHEMATICAL PROGRAMMING COMPUTATION 2017年第2期9卷 135-202页

作者： Hougardy, Stefan Silvanus, Jannik Vygen, Jens Univ Bonn Res Inst Discrete Math Bonn Germany

We present a new exact algorithm for the Steiner tree problem in edgeweighted graphs. Our algorithm improves the classical dynamic programming approach by Dreyfus and Wagner. We achieve a significantly better practical performance via pruning and future costs, a generalization of a well-known concept to speed up shortest path computations. Our algorithm matches the best known worst-case run time and has a fast, often superior, practical performance: on some large instances originating from VLSI design, previous best run times are improved upon by orders of magnitudes. We are also able to solve larger instances of the d-dimensional rectilinear Steiner tree problem for d is an element of{3, 4, 5}, whose Hanan grids contain up to several millions of edges.

关键词： Graph algorithms Steiner tree problem Dynamic programming exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Parameterized and exact algorithms for class domination coloring

引用

DISCRETE APPLIED MATHEMATICS 2021年 291卷 286-299页

作者： Krithika, R. Rai, Ashutosh Saurabh, Saket Tale, Prafullkumar Indian Inst Technol Palakkad Palakkad India IIT Dept Math Delhi India HBNI Inst Math Sci Chennai Tamil Nadu India Univ Bergen Bergen Norway CISPA Helmholtz Ctr Informat Secur Saarbrucken Germany

A class domination coloring (also called cd-Coloring or dominated coloring) of a graph is a proper coloring in which every color class is contained in the neighborhood of some vertex. The minimum number of colors required for any cd-coloring of G, denoted by chi(cd)(G), is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q, can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q? For the first problem, we give an exact algorithm with running time O(2(n)n(4) log n). Also, we show that the problem is FPT with respect to the number q of colors as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O(q(3)) vertices. For the second (deletion) problem, we show NP-hardness for each q >= 2. Further, on split graphs, we show that the problem is NP-hard if q is a part of the input and FPT with respect to k and q as combined parameters. As recognizing graphs with cd-chromatic number at most q is NP-hard in general for q >= 4, the deletion problem is unlikely to be FPT when parameterized by the size of the deletion set on general graphs. We show fixed parameter tractability for q is an element of {2, 3} using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. (C) 2020 Elsevier B.V. All rights reserved.

关键词： Class domination coloring Fixed parameter tractable exact algorithm NP hardness Chordal and split graphs

来源：评论

学校读者我要写书评

暂无评论

An exact DSatur-based algorithm for the Equitable Coloring Problem

引用

Electronic Notes in Discrete Mathematics 2013年第0期44卷 281-286页

作者： Méndez-Díaz, Isabel Nasini, Graciela Severín, Daniel FCEyN Universidad de Buenos Aires Argentina FCEIA Universidad Nacional de Rosario y CONICET Argentina Argentina

This paper describes an exact algorithm for the Equitable Coloring Problem, based on the well known DSatur algorithm for the classic Coloring Problem with new pruning rules specifically derived from the equity constraint. Computational experiences show that our algorithm is competitive with those known in literature. © 2013 Elsevier B.V.

关键词： DSatur Equitable coloring exact algorithm

来源：评论

学校读者我要写书评

暂无评论

Fast exact algorithms for Optimization Problems in Resource Allocation and Switched Linear Systems

Fast Exact Algorithms for Optimization Problems in Resource ...

引用

作者： Wu, Zeyang University of Minnesota

学位级别：Ph.D.

Discrete optimization is a branch of mathematical optimization where some of the decision variables are restricted to real values in a discrete set. The use of discrete decision variables greatly expands the scope and capacity of mathematical optimization models. In the era of big data, efficiency and scalability are increasingly important in evaluating the performance of an algorithm. However, discrete optimization problems usually are challenging to solve. In this thesis, we develop new fast exact algorithms for discrete optimization problems arising in the field of resource allocation and switched linear systems. The first problem is the discrete resource allocation problem with nested bound constraints. It is a fundamental problem with a wide variety of applications in search theory, economics, inventory systems, etc. Given B units of resource and n activities, each of which associated with a convex allocation cost fi(·), we aim to find an allocation of resources to the n activities, denoted by x ∈ Zn, to minimize the total allocation cost ∑ni=0di subject to the total amount of resource constraint as well as lower and upper bound constraints on total resource allocated to subsets of activities. We develop a Θ(n2logB/n)-time algorithm for it. It is an infeasibility-guided divide-and-conquer algorithm and the worst-case complexity is usually not achieved. Numerical experiments demonstrate that our algorithm significantly outperforms a state-of-the-art optimization solver and the performance of our algorithm is competitive compared to the algorithm with the best worst-case complexity for this problem in the literature. The second problem is the minimum convex cost network flow problem on the dynamic lot size network. In the dynamic lot size network, there are one source node and n sink nodes with demand di, i = 1,...,n. Let B = ∑ni=0di be the total demand. We aim to find a flow x to minimize the total arc cost and satisfy all the flow balance and capacity constrain

关键词： exact algorithm Mixed-integer program Resource allocation Switched linear systems

来源：评论

学校读者我要写书评

暂无评论

An exact and polynomial distance-based algorithm to reconstruct single copy tandem duplication trees

引用

JOURNAL OF DISCRETE algorithmS 2005年第2-4期3卷 362-374页

作者： Elemento, Olivier Gascuel, Olivier Princeton Univ Lewis Sigler Inst Integrat Gen Princeton NJ 08544 USA LIRMM Equipe Methodes & Algorithmes Bioinformat 161 Rue Ada F-34392 Montpellier France

The problem of reconstructing the duplication tree of a set of tandemly repeated sequences which are supposed to have arisen by unequal recombination, was first introduced by Fitch (1977), and has recently received a lot of attention. In this paper, we place ourselves in a distance framework and deal with the restricted problem of reconstructing single copy duplication trees. We describe an exact and polynomial distance based algorithm for solving this problem, the parsimony version of which has previously been shown to be NP-hard (like most evolutionary tree reconstruction problems). This algorithm is based on the minimum evolution principle, and thus involves selecting the shortest tree as being the correct duplication tree. After presenting the underlying mathematical concepts behind theminimum evolution principle, and some of its benefits (such as statistical consistency), we provide a new recurrence formula to estimate the tree length using ordinary least-squares, given a matrix of pairwise distances between the copies. We then show how this formula naturally forms the dynamic programming framework on which our algorithm is based, and provide an implementation in O(n3) time and O(n(2)) space, where n is the number of copies. (C) 2004 Elsevier B. V. All rights reserved.

关键词： Evolution reconstructions Phylogenetic trees Duplication trees Tandemly repeated sequences Gene families Distance-based methods Least-squares Minimum evolution principle exact algorithm Dynamic programming

来源：评论

学校读者我要写书评

暂无评论

A Measure & Conquer Approach for the Analysis of exact algorithms

引用

JOURNAL OF THE ACM 2009年第5期56卷 25-25:32页

作者： Fomin, Fedor V. Grandoni, Fabrizio Kratsch, Dieter Univ Bergen Dept Informat N-5020 Bergen Norway Univ Roma Tor Vergata Dipartimento Informat Sistemi & Prod I-00133 Rome Italy Univ Paul Verlaine LITA F-57045 Metz 01 France Univ Roma Tor Vergata Rome Italy

For more than 40 years, Branch & Reduce exponential-time backtracking algorithms have been among the most common tools used for finding exact solutions of NP-hard problems. Despite that, the way to analyze such recursive algorithms is still far from producing tight worst-case running time bounds. Motivated by this, we use an approach, that we call "Measure& Conquer", as an attempt to step beyond such limitations. The approach is based on the careful design of a nonstandard measure of the subproblem size;this measure is then used to lower bound the progress made by the algorithm at each branching step. The idea is that a smarter measure may capture behaviors of the algorithm that a standard measure might not be able to exploit, and hence lead to a significantly better worst-case time analysis. In order to show the potentialities of Measure & Conquer, we consider two well-studied NP-hard problems: minimum dominating set and maximum independent set. For the first problem, we consider the current best algorithm, and prove (thanks to a better measure) a much tighter running time bound for it. For the second problem, we describe a new, simple algorithm, and show that its running time is competitive with the current best time bounds, achieved with far more complicated algorithms (and standard analysis). Our examples show that a good choice of the measure, made in the very first stages of exact algorithms design, can have a tremendous impact on the running time bounds achievable.

关键词： algorithms Theory Dominating set exact algorithm independent set

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：