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

41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016

作者： Ganian, Robert Narayanaswamy, N.S. Ordyniak, Sebastian Rahul, C.S. Ramanujan, M.S. Algorithms and Complexity Group TU Wien Vienna Austria Indian Institute of Technology Madras Chennai India FI MU Brno Czech Republic

ISBN: (纸本)9783959770163

Given an n-vertex graph G and a function f : V (G) → {0, . . . , n-1}, an f-factor is a subgraph H of G such that degH(v) = f(v) for every vertex v ϵ V (G);we say that H is a connected f-factor if, in addition, the subgraph H is connected. A classical result of Tutte (1954) is the polynomial time algorithm to check whether a given graph has a specified f-factor. However, checking for the presence of a connected f-factor is easily seen to generalize Hamiltonian Cycle and hence is NP-complete. In fact, the Connected f-Factor problem remains NP-complete even when f(v) is at least nϵ for each vertex v and ϵ c, the problem can be solved in quasi-polynomial time in general and in randomized polynomial time if c ≤ 1. We also show that when c > 1, the problem is NP-intermediate. © Robert Ganian, Ronald de Haan, Iyad Kanj, and Stefan Szeider.

关键词： Computational complexity

来源：评论

学校读者我要写书评

暂无评论

Vertices of Degree k in Random Unlabeled Trees

引用

Electronic Notes in Discrete Mathematics 2009年 34卷 41-45页

作者： Panagiotou, Konstantinos Sinha, Makrand Department of Algorithms and Complexity Max-Planck-Institute for Informatics 66123 Saarbrücken Germany Department of Computer Science and Engineering Indian Institute of Technology Kanpur 208016 Kanpur India

Let Hn be the class of vertex-rooted unlabeled trees with n vertices, and denote by Hn a tree that is drawn uniformly at random from this set. In this work we study the number degk (Hn) of vertices of degree k in Hn. ... 详细信息

Let H_n be the class of vertex-rooted unlabeled trees with n vertices, and denote by H_n a tree that is drawn uniformly at random from this set. In this work we study the number deg_k (H_n) of vertices of degree k in H_n. In particular, for k = O ((frac(log n, log log n))^{1 / 2}) we show exponential-type bounds for the probability that deg_k (H_n) deviates from its expectation. On the technical side, our proofs are based on the analysis of a randomized algorithm that generates unlabeled trees in the so-called Boltzmann model. The analysis of such algorithms is quite well-understood for classes of labeled graphs. Comparable algorithms for unlabeled classes are unfortunately much more complex. We demonstrate in this work that they can be analyzed very precisely for classes of unlabeled graphs as well. © 2009 Elsevier B.V. All rights reserved.

关键词： Boltzmann Sampling Degree Sequence Random Unlabeled Trees

来源：评论

学校读者我要写书评

暂无评论

Balanced Connected Subgraph Problem in Geometric Intersection Graphs 1

引用

13th Annual International Conference on Combinatorial Optimization and Applications, COCOA 2019

作者： Bhore, Sujoy Jana, Satyabrata Pandit, Supantha Roy, Sasanka Algorithms and Complexity Group TU Wien Vienna Austria Indian Statistical Institute Kolkata India Dhirubhai Ambani Institute of Information and Communication Technology GandhinagarGujarat India

ISBN: (数字)9783030364120

ISBN: (纸本)9783030364113

We study the (shortly,) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given agraph, where each vertex in V is colored with either "" or "", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is, i.e., H contains an equal number of red and blue vertices. We study the computational complexity landscape of the BCS problem while considering geometric intersection graphs. On one hand, we prove that the BCS problem is NP-hard on the unit disk, outer-string, complete grid, and unit square graphs. On the other hand, we design polynomial-time algorithms for the BCS problem on interval, circular-arc and permutation graphs. In particular, we give algorithms for theproblem on both interval and circular-arc graphs, and those algorithms are used as subroutines for solving the BCS problem on the same classes of graphs. Finally, we present a FPT algorithm for the BCS problem on general graphs. © 2019, Springer Nature Switzerland AG.

关键词： Polynomial approximation

来源：评论

学校读者我要写书评

暂无评论

No Polynomial Kernels for Knapsack 51

No Polynomial Kernels for Knapsack

引用

51st International Colloquium on Automata, Languages, and Programming, ICALP 2024

作者： Heeger, Klaus Hermelin, Danny Mnich, Matthias Shabtay, Dvir Department of Industrial Engineering and Management Ben-Gurion University of the Negev Beer-Sheva Israel Institute for Algorithms and Complexity Hamburg University of Technology Hamburg Germany

ISBN: (纸本)9783959773225

This paper focuses on kernelization algorithms for the fundamental Knapsack problem. A kernelization algorithm (or kernel) is a polynomial-time reduction from a problem onto itself, where the output size is bounded by a function of some problem-specific parameter. Such algorithms provide a theoretical model for data reduction and preprocessing and are central in the area of parameterized complexity. In this way, a kernel for Knapsack for some parameter k reduces any instance of Knapsack to an equivalent instance of size at most f(k) in polynomial time, for some computable function f. When f(k) = kO(1) then we call such a reduction a polynomial kernel. Our study focuses on two natural parameters for Knapsack: The number w# of different item weights, and the number p# of different item profits. Our main technical contribution is a proof showing that Knapsack does not admit a polynomial kernel for any of these two parameters under standard complexity-theoretic assumptions. Our proof discovers an elaborate application of the standard kernelization lower bound framework, and develops along the way novel ideas that should be useful for other problems as well. We complement our lower bounds by showing that Knapsack admits a polynomial kernel for the combined parameter w# · p#. © Klaus Heeger, Danny Hermelin, Matthias Mnich, and Dvir Shabtay.

关键词： Profitability

来源：评论

学校读者我要写书评

暂无评论

A (3/2 + Ε)-Approximation for Multiple TSP with a Variable Number of Depots

arXiv

引用

arXiv 2023年

作者： Deppert, Max Kaul, Matthias Mnich, Matthias Hamburg University of Technology Institute for Algorithms and Complexity Germany

One of the most studied extensions of the famous Traveling Salesperson Problem (TSP) is the Multiple TSP: a set of m ≥ 1 salespersons collectively traverses a set of n cities by m non-trivial tours, to minimize the total length of their tours. This problem can also be considered to be a variant of Uncapacitated Vehicle Routing, where the objective is to minimize the sum of all tour lengths. When all m tours start from and end at a single common depot v0, then the metric Multiple TSP can be approximated equally well as the standard metric TSP, as shown by Frieze (1983). The metric Multiple TSP becomes significantly harder to approximate when there is a set D of d ≥ 1 depots that form the starting and end points of the m tours. For this case, only a (2 − 1/d)-approximation in polynomial time is known, as well as a 3/2-approximation for constant d which requires a prohibitive run time of nΘ(d) (Xu and Rodrigues, INFORMS J. Comput., 2015). A recent work of Traub, Vygen and Zenklusen (STOC 2020) gives another approximation algorithm for metric Multiple TSP with run time nΘ(d), which reduces the problem to approximating metric TSP. In this paper we overcome the nΘ(d) time barrier: we give the first efficient approximation algorithm for Multiple TSP with a variable number d of depots that yields a better-than-2 approximation. Our algorithm runs in time (1/Ε)O(dlog d)·nO(1), and produces a (3/2+Ε)-approximation with constant probability. For the graphic case, we obtain a deterministic 3/2-approximation in time 2d · nO(1) Copyright © 2023, The Authors. All rights reserved.

关键词： Vehicle routing

来源：评论

学校读者我要写书评

暂无评论

Exact bounds for distributed graph colouring 1

引用

22nd International Colloquium on Structural Information and Communication complexity, SIROCCO 2015

作者： Rybicki, Joel Suomela, Jukka Helsinki Institute for Information Technology HIIT Department of Computer Science Aalto University Saarbrücken Finland Department of Algorithms and Complexity Max Planck Institute for Informatics Saarbrücken Germany

ISBN: (数字)9783319252582

ISBN: (纸本)9783319252575

We prove exact bounds on the time complexity of distributed graph colouring. If we are given a directed path that is properly coloured with n colours, by prior work it is known that we can find a proper 3-colouring (Formula presented.)in communication rounds. We close the gap between upper and lower bounds: we show that for infinitely many n the time complexity is precisely (Formula presented.) communication rounds. © Springer International Publishing Switzerland 2015.

关键词： Graph theory

来源：评论

学校读者我要写书评

暂无评论

Coloring random graphs online without creating monochromatic subgraphs 11

Coloring random graphs online without creating monochromatic...

引用

Annual ACM-Society for Industrial and Applied Mathmatics Symposium on Discrete algorithms

作者： Torsten Mutze Thomas Rast Reto Spohel Institute of Theoretical Computer Science Algorithms and Complexity Group

ISBN: (纸本)9780898719932

Consider the following generalized notion of graph coloring: a coloring of the vertices of a graph G is valid w.r.t. some given graph F if there is no copy of F in G whose vertices all receive the same color. We study the problem of computing valid colorings of the binomial random graph G_(n,p) on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of G_(n,p) are revealed one by one (together with all edges leading to previously revealed vertices) and have to be colored immediately and irrevocably with one of r available colors. It is known that for any fixed graph F and any fixed integer r≥2 this problem has a threshold p0(F, r, n) in the following sense: For any function p(n) = o(p0) there is a strategy that a.a.s. (asymptotically almost surely, i.e., with probability tending to 1 as n tends to infinity) finds an r-coloring of G_(n,p) that is valid w.r.t. F online, and for any function p(n)=ω(p0) any online strategy will a.a.s. fail to do so. In this work we establish a general correspondence between this probabilistic problem and a deterministic twoplayer game in which the random process is replaced by an adversary that is subject to certain restrictions inherited from the random setting. This characterization allows us to compute, for any F and r, a valueγ=γ(F,r) such that the threshold of the probabilistic problem is given by p0(F, r, n) = n~(-γ). Our approach yields polynomial-time coloring algorithms that a.a.s. find valid colorings of G_(n,p) online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n~(-γ)).

关键词： Color Fluorine (F) vertex head Valid AASS gene colored graph Line graph Probability Stochastic Processes

来源：评论

学校读者我要写书评

暂无评论

On the parameterized complexity of simultaneous deletion problems 37

On the parameterized complexity of simultaneous deletion pro...

引用

37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2017

作者： Agrawal, Akanksha Krithika, R. Lokshtanov, Daniel Mouawad, Amer E. Ramanujan, M.S. Department of Informatics University of Bergen Bergen Norway Institute of Mathematical Sciences HBNI Chennai India Algorithms and Complexity Group Vienna University of Technology Vienna Austria

ISBN: (纸本)9783959770552

For a family of graphs F, an n-vertex graph G, and a positive integer k, the F-Deletion problem asks whether we can delete at most k vertices from G to obtain a graph in F. F-Deletion generalizes many classical graph problems such as Vertex Cover, Feedback Vertex Set, and Odd Cycle Transversal. A (multi) graph G = (V, ?ai=1Ei), where the edge set of G is partitioned into a color classes, is called an a-edge-colored graph. A natural extension of the F-Deletion problem to edge-colored graphs is the Simultaneous (F1, . . ., Fa)-Deletion problem. In the latter problem, we are given an a-edge-colored graph G and the goal is to find a set S of at most k vertices such that each graph Gi - S, where Gi = (V, Ei) and 1 = i = a, is in Fi. Recently, a subset of the authors considered the aforementioned problem with F1 = . . . = Fa being the family of all forests. They showed that the problem is fixed-parameter tractable when parameterized by k and a and can be solved in O(2O(ak)) time1. In this work, we initiate the investigation of the complexity of Simultaneous (F1, . . ., Fa)-Deletion with di erent families of graphs. In the process, we obtain a complete characterization of the parameterized complexity of this problem when one or more of the Fis is the class of bipartite graphs and the rest (if any) are forests. We show that if F1 is the family of all bipartite graphs and each of F2 = F3 = . . . = Fa is the family of all forests then the problem is fixed-parameter tractable parameterized by k and a. However, even when F1 and F2 are both the family of all bipartite graphs, then the Simultaneous (F1, F2)-Deletion problem itself is already W[1]-hard. © Akanksha Agrawal, R. Krithika, Daniel Lokshtanov, Amer E. Mouawad, and M. S. Ramanujan.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Further Exploiting c-Closure for FPT algorithms and Kernels for Domination Problems 39

Further Exploiting c-Closure for FPT Algorithms and Kernels ...

引用

39th International Symposium on Theoretical Aspects of Computer Science, STACS 2022

作者： Kanesh, Lawqueen Madathil, Jayakrishnan Roy, Sanjukta Sahu, Abhishek Saurabh, Saket National University of Singapore Singapore Chennai Mathematical Institute India Algorithms and Complexity Group TU Wien Austria The Institute of Mathematical Sciences HBNI Chennai India University of Bergen Norway

ISBN: (纸本)9783959772228

For a positive integer c, a graph G is said to be c-closed if every pair of non-adjacent vertices in G have at most c - 1 neighbours in common. The closure of a graph G, denoted by cl(G), is the least positive integer c for which G is c-closed. The class of c-closed graphs was introduced by Fox et al. [ICALP ‘18 and SICOMP ‘20]. Koana et al. [ESA ‘20] started the study of using cl(G) as an additional structural parameter to design kernels for problems that are W-hard under standard parameterizations. In particular, they studied problems such as Independent Set, Induced Matching, Irredundant Set and (Threshold) Dominating Set, and showed that each of these problems admits a polynomial kernel, either w.r.t. the parameter k + c or w.r.t. the parameter k for each fixed value of c. Here, k is the solution size and c = cl(G). The work of Koana et al. left several questions open, one of which was whether the Perfect Code problem admits a fixed-parameter tractable (FPT) algorithm and a polynomial kernel on c-closed graphs. In this paper, among other results, we answer this question in the affirmative. Inspired by the FPT algorithm for Perfect Code, we further explore two more domination problems on the graphs of bounded closure. The other problems that we study are Connected Dominating Set and Partial Dominating Set. We show that Perfect Code and Connected Dominating Set are fixed-parameter tractable w.r.t. the parameter k + cl(G), whereas Partial Dominating Set, parameterized by k is W[1]-hard even when cl(G) = 2. We also show that for each fixed c, Perfect Code admits a polynomial kernel on the class of c-closed graphs. And we observe that Connected Dominating Set has no polynomial kernel even on 2-closed graphs, unless NP ⊆ co-NP/poly. © Lawqueen Kanesh, Jayakrishnan Madathil, Sanjukta Roy, Abhishek Sahu, and Saket Saurabh.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Exponentially faster fixed-parameter algorithms for high-multiplicity scheduling

arXiv

引用

arXiv 2022年

作者： Fischer, David Golak, Julian Mnich, Matthias Hamburg University Of Technology Institute For Algorithms And Complexity Germany

We consider so-called N-fold integer programs (IPs) of the form max{cTx : Ax = b, ≤ x ≤ u, x ∈ nt}, where A ∈ (r+sn)×ntconsists of n arbitrary matrices A(i)∈ r×ton a horizontal, and n arbitrary matrices B(j)∈ Zs×ton a diagonal line. Several recent works design fixed-parameter algorithms for N-fold IPs by taking as parameters the numbers of rows and columns of the A- and B-matrices, together with the largest absolute value Δ over their entries. These advances provide fast algorithms for several well-studied combinatorial optimization problems on strings, on graphs, and in machine scheduling. In this work, we extend this research by proposing algorithms that additionally harness a partition structure of submatrices A(i)and B(j), where row indices of non-zero entries do not overlap between any two sets in the partition. Our main result is an algorithm for solving any N-fold IP in time ntlog(nt)L(SA)O(r+s)(pApBΔ)O(rpApB+spApB), where pA and pB are the size of the largest set in such a partition of A(i)and B(j), respectively, SAis the number of parts in the partition of A = (A(1), ⋯, A(n)), and L = (log(||u - ||∞)·(log(maxx:≤x≤u|cTx|)) is a measure of the input. We show that these new structural parameters are naturally small in high-multiplicity scheduling problems, such as makespan minimization on related and unrelated machines, with and without release times, the Santa Claus objective, and the weighted sum of completion times. In essence, we obtain algorithms that are exponentially faster than previous works by Knop et al. (ESA 2017) and Eisenbrand et al./Koutecký et al. (ICALP 2018) in terms of the number of job types. We also improve the complexity of minimum sum coloring on graphs of bounded neighborhood diversity. Copyright © 2022, The Authors. All rights reserved.

关键词： Integer programming

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：