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

New algorithms for Maximum Weight Matching and a Decomposition Theorem

MATHEMATICS OF OPERATIONS RESEARCH 2017年第2期42卷 411-426页

作者： Huang, Chien-Chung Kavitha, Telikepalli Chalmers Univ Technol Gothenburg Sweden Tata Inst Fundamental Res Bombay Maharashtra India

We revisit the classical maximum weight matching problem in general graphs with nonnegative integral edge weights. We present an algorithm that operates by decomposing the problem into W unweighted versions of the problem, where W is the largest edge weight. Our algorithm has running time as good as the current fastest algorithms for the maximum weight matching problem when W is small. One of the highlights of our algorithm is that it also produces an integral optimal dual solution;thus our algorithm also returns an integral certificate corresponding to the maximum weight matching that was computed. Our algorithm yields a new proof to the total dual integrality of Edmonds' matching polytope and it also gives rise to a decomposition theorem for the maximum weight of a matching in terms of the maximum size of a matching in certain subgraphs. We also consider the maximum weight capacitated b-matching problem in bipartite graphs with nonnegative integral edge weights and show that it can also be decomposed into W unweighted versions of the problem, where W is the largest edge weight. Our second algorithm is competitive with known algorithms when W is small.

关键词： maximum weight matching exact algorithms total dual integrality

来源：评论

学校读者我要写书评

暂无评论

Complexity of independency and cliquy trees

引用

DISCRETE APPLIED MATHEMATICS 2020年第0期272卷 2-15页

作者： Casel, Katrin Dreier, Jan Fernau, Henning Gobbert, Moritz Kuinke, Philipp Villaamil, Fernando Sanchez Schmid, Markus L. van Leeuwen, Erik Jan Univ Trier CIRT Fachbereich 4 Abt Informatikwissensch D-54286 Trier Germany Univ Utrecht Dept Informat & Comp Sci POB 80-089 NL-3508 TB Utrecht Netherlands Rhein Westfal TH Aachen Lehr & Forschungsgebiet Theoret Informat D-52074 Aachen Germany Univ Potsdam Hasso Plattner Inst D-14482 Potsdam Germany

An independency (cliquy) tree of an n-vertex graph G is a spanning tree of G in which the set of leaves induces an independent set (clique). We study the problems of minimizing or maximizing the number of leaves of such trees, and fully characterize their parameterized complexity. We show that all four variants of deciding if an independency/cliquy tree with at least/most l leaves exists parameterized by l are either Para-NP- or W[1]-hard. We prove that minimizing the number of leaves of a cliquy tree parameterized by the number of internal vertices is Para-NP-hard too. However, we show that minimizing the number of leaves of an independency tree parameterized by the number k of internal vertices has an O*(4(k))-time algorithm and a 2k vertex kernel. Moreover, we prove that maximizing the number of leaves of an independency/cliquy tree parameterized by the number k of internal vertices both have an O*(18(k))-time algorithm and an O(k 2(k)) vertex kernel, but no polynomial kernel unless the polynomial hierarchy collapses to the third level. Finally, we present an O(3(n) . f(n))-time algorithm to find a spanning tree where the leaf set has a property that can be decided in f (n) time and has minimum or maximum size. (C) 2018 Elsevier B.V. All rights reserved.

关键词： Independency tree Cliquy tree Parameterized complexity Kernelization algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Mathematical models for stable matching problems with ties and incomplete lists

引用

EUROPEAN JOURNAL OF OPERATIONAL RESEARCH 2019年第2期277卷 426-441页

作者： Delorme, Maxence Garcia, Sergio Gondzio, Jacek Kalcsics, Joerg Manlove, David Pettersson, William Univ Edinburgh Sch Math Edinburgh Midlothian Scotland Univ Glasgow Sch Comp Sci Glasgow Lanark Scotland

We present new integer linear programming (ILP) models for NP-hard optimisation problems in instances of the Stable Marriage problem with Ties and Incomplete lists (SMTI) and its many-to-one generalisation, the Hospitals/Residents problem with Ties (HRT). These models can be used to efficiently solve these optimisation problems when applied to (i) instances derived from real-world applications, and (ii) larger instances that are randomly-generated. In the case of SMTI, we consider instances arising from the pairing of children with adoptive families, where preferences are obtained from a quality measure of each possible pairing of child to family. In this case, we seek a maximum weight stable matching. We present new algorithms for preprocessing instances of SMTI with ties on both sides, as well as new ILP models. algorithms based on existing state-of-the-art models only solve 6 of our 22 real-world instances within an hour per instance, and our new models incorporating dummy variables and constraint merging, together with preprocessing and a warm start, solve all 22 instances within a mean runtime of a minute. For HRT, we consider instances derived from the problem of assigning junior doctors to foundation posts in Scottish hospitals. Here, we seek a maximum size stable matching. We show how to extend our models for SMTI to HRT and reduce the average running time for real-world HRT instances by two orders of magnitude. We also show that our models outperform by a wide margin all known state-of-the-art models on larger randomly-generated instances of SMTI and HRT. (C) 2019 The Authors. Published by Elsevier B.V.

关键词： Assignment Stable Marriage problem Hospitals/Residents problem Ties and Incomplete lists exact algorithms

来源：评论

学校读者我要写书评

暂无评论

Induced star partition of graphs

引用

DISCRETE APPLIED MATHEMATICS 2022年 319卷 81-91页

作者： Shalu, M. A. Vijayakumar, S. Sandhya, T. P. Mondal, Joyashree Indian Inst Informat Technol Design & Mfg IIITDM Chennai 600127 India Univ Passau Dept Comp Sci & Math Passau Germany

Given a graph G, we call a partition (V-1, V-2, ... , V-k) of its vertex set an induced star partition of G if each set in the partition induces a star. In this paper, we consider the problem of finding an induced star partition of a graph of minimum size and its decision versions. This problem may be viewed as an amalgamation of the well-known dominating set and coloring problems. We obtain the following main results: (1) Deciding whether a graph can be partitioned into k induced stars is NP-complete for each fixed k >= 3 and has a polynomial time algorithm for each k <= 2. (2) It is NP-hard to approximate the minimum induced star partition size within n(1/2-epsilon )for all epsilon > 0. (3) The decision version of the induced star partition problem is NP-complete for subcubic bipartite planar graphs, line graphs (a subclass of K-1,K-r-free graphs, r >= 3), K-1,K-5-free split graphs and co-tripartite graphs. (4) The minimum induced star partition problem has an r/2 -approximation algorithm for K-1,K-r-free graphs (r >= 2) and a 2-approximation algorithms for split graphs. We also identify some fixed parameter tractable and exact exponential time algorithms that follow from the literature. (c) 2021 Elsevier B.V. All rights reserved.

关键词： Induced star partition Polynomial time algorithms NP-completeness Approximation algorithms FPT exact algorithms

来源：评论

学校读者我要写书评

暂无评论

A fixed-parameter tractability result for multicommodity demand flow in trees

引用

INFORMATION PROCESSING LETTERS 2006年第3期97卷 109-114页

作者： Guo, J Niedermeier, R Univ Jena Inst Informat D-07743 Jena Germany

We study an NP-hard (and MaxSNP-hard) problem in trees-MULTICOMMODITY DEMAND FLOW-dealing with demand flows between pairs of nodes and trying to maximize the value of the routed flows. This problem has been intensively studied for trees as well as for general graphs mainly from the viewpoint of polynomial-time approximation algorithms. By way of contrast, we provide an exact dynamic programming algorithm for this problem that works well whenever some natural problem parameter is small, a reasonable assumption in several applications. More specifically, we prove fixed-parameter tractability with respect to the maximum number of the input flows at any tree node. (c) 2005 Elsevier B.V. All rights reserved.

关键词： combinatorial problems graph algorithms NP-hard problems exact algorithms fixed-parameter tractability

来源：评论

学校读者我要写书评

暂无评论

The max quasi-independent set problem

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2012年第1期23卷 94-117页

作者： Bourgeois, N. Giannakos, A. Lucarelli, G. Milis, I. Paschos, V. T. Pottie, O. CNRS LAMSADE FRE 3234 Paris France Univ Paris 09 Paris France Athens Univ Econ & Business Dept Informat Athens Greece

In this paper, we deal with the problem of finding quasi-independent sets in graphs. This problem is formally defined in three versions, which are shown to be polynomially equivalent. The one that looks most general, namely, f -MAX QUASIINDEPENDENT SET, consists of, given a graph and a non-decreasing function f, finding a maximum size subset Q of the vertices of the graph, such that the number of edges in the induced subgraph is less than or equal to f (|Q|). For this problem, we show an exact solution method that runs within time O*(2(d-27/23/d+1 n)) on graphs of average degree bounded by d. For the most specifically defined gamma-MAX QUASI-INDEPENDENT SET and k-MAX QUASI-INDEPENDENT SET problems, several results on complexity and approximation are shown, and greedy algorithms are proposed, analyzed and tested.

关键词： Quasi independent set exact algorithms Approximation algorithms

来源：评论

学校读者我要写书评

暂无评论

Advice complexity of adaptive priority algorithms

引用

THEORETICAL COMPUTER SCIENCE 2024年 984卷

作者： Boyar, Joan Larsen, Kim S. Pankratov, Denis Univ Southern Denmark Dept Math & Comp Sci Campusvej 55 DK-5230 Odense M Denmark Concordia Univ Dept Comp Sci & Software Engn 2155 Guy St Montreal PQ H3H 2L9 Canada

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. As evidence that adding advice to adaptive priority algorithms extends both adaptive priority algorithms and online algorithms with advice, we present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.

关键词： Greedy algorithms Priority algorithms Adaptive priority algorithms exact algorithms Online algorithms Advice complexity

来源：评论

学校读者我要写书评

暂无评论

Uniformity of quantum circuit families for error-free algorithms

引用

THEORETICAL COMPUTER SCIENCE 2005年第1-3期332卷 487-496页

作者： Nishimura, H Ozawa, M Japan Sci & Technol Agcy ERATO Quantum Comp & Informat Project Kamigyo Ku Kyoto 6020873 Japan Tohoku Univ Grad Sch Informat Sci Sendai Miyagi 9808579 Japan

In order to establish the computational equivalence between quantum Turing machines (QTMs') and quantum circuit families (QCFs) using Yao's quantum circuit simulation of QTMs, we have previously introduced the class of uniform QCFs based on an infinite set of elementary gates, which has been shown to be computationally equivalent to polynomial-time QTMs up to bounded error simulation. However, the complexity classes ZQP and EQP introduced by Bernstein and Vazirani for QTMs do not appear to equal their counterparts for uniform QCFs. Recently, we have introduced a subclass of uniform QCFs, the class of finitely generated uniform QCFs, and showed that they are perfectly equivalent to the class of polynomial-time QTMs in the sense that both classes can be exactly simulated with each other. Here, we further investigate the power of uniform QCFs comparing with that of finitely generated uniform QCFs in detail. We obtain the following results: (i) If a permutation M-f : vertical bar x > -> vertical bar f (x)> can be implemented with zero error by a uniform QCF, then both f and f(-1) can be exactly computed by uniform QCFs. (ii) The quantum Fourier transform (QFT) of any order cannot be implemented with zero error by any finitely generated uniform QCF, while it has been shown, in contrast, by Mosca and Zalka that the QFT of any order can be exactly implemented by a uniform QCE. (c) 2005 Elsevier B.V. All rights reserved.

关键词： quantum computation complexity theory uniform circuit families zero-error algorithms exact algorithms

来源：评论

学校读者我要写书评

暂无评论

An improved exact algorithm for the domatic number problem

引用

INFORMATION PROCESSING LETTERS 2007年第3期101卷 101-106页

作者： Riege, Tobias Rothe, Joerg Spakowski, Holger Yamamoto, Masaki Univ Dusseldorf Inst Informat D-4000 Dusseldorf Germany Tokyo Inst Technol Dept Math & Comp Sci Tokyo 152 Japan

The 3-domatic number problem asks whether a given graph can be partitioned into three dominating sets. We prove that this problem can be solved by a deterministic algorithm in time 2.695(n) (up to polynomial factors) and in polynomial space. This result improves the previous bound of 2.8805(n), which is due to Bjorklund and Husfeldt. To prove our result, we combine an algorithm by Fomin et al. with Yamamoto's algorithm for the satisfiability problem. In addition, we show that the 3-domatic number problem can be solved for graphs G with bounded maximum degree Delta (G) by a randomized polynomial-space algorithm, whose running time is better than the previous bound due to Riege and Rothe whenever Delta (G) >= 5. Our new randomized algorithm employs Schoning's approach to constraint satisfaction problems. (c) 2006 Elsevier B.V. All rights reserved.

关键词： graph algorithms exact algorithms randomized algorithms domatic number problem

来源：评论

学校读者我要写书评

暂无评论

A refined algorithm for maximum independent set in degree-4 graphs

引用

JOURNAL OF COMBINATORIAL OPTIMIZATION 2017年第3期34卷 830-873页

作者： Xiao, Mingyu Nagamochi, Hiorshi Univ Elect Sci & Technol China Sch Comp Sci & Engn Chengdu 610054 Peoples R China Kyoto Univ Grad Sch Informat Dept Appl Math & Phys Sakyo Ku Kyoto 6068501 Japan

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of "shift" to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree , which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree . Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.

关键词： exact algorithms Graph algorithms Maximum independent set Measure-and-conquer Amortized analysis

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：