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

作者： Mütze, Torsten Rast, Thomas Spöhel, Reto Institute of Theoretical Computer Science ETH Zürich 8092 Zürich Switzerland Algorithms and Complexity Group Max-Planck-Institut für Informatik 66123 Saarbrücken Germany

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 Gn,p on n vertices with edge probability p = p(n) in the following online setting: the vertices of an initially hidden instance of Gn,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 Gn,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 two-player 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 Gn,p online in the entire regime below the respective thresholds, i.e., for any p(n) = o(n-γ).

关键词： Coloring

来源：评论

学校读者我要写书评

暂无评论

On the Upward Book Thickness Problem: Combinatorial and complexity Results 29th

On the Upward Book Thickness Problem: Combinatorial and Com...

引用

29th International Symposium on Graph Drawing and Network Visualization, GD 2021

作者： Bhore, Sujoy Da Lozzo, Giordano Montecchiani, Fabrizio Nöllenburg, Martin Indian Institute of Science Education and Research Bhopal India Roma Tre University Rome Italy Department of Engineering University of Perugia Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria

ISBN: (纸本)9783030929305

A long-standing conjecture by Heath, Pemmaraju, and Trenk states that the upward book thickness of outerplanar DAGs is bounded above by a constant. In this paper, we show that the conjecture holds for subfamilies of upward outerplanar graphs, namely those whose underlying graph is an internally-triangulated outerpath or a cactus, and those whose biconnected components are st-outerplanar graphs. On the complexity side, it is known that deciding whether a graph has upward book thickness k is NP-hard for any fixed k≥ 3. We show that the problem, for any k≥ 5, remains NP-hard for graphs whose domination number is O(k), but it is FPT in the vertex cover number. © 2021, Springer Nature Switzerland AG.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

Representing series-parallel graphs as intersection graphs of line segments in three directions

引用

3rd Asian Applied Computing Conference, AACC 2005

作者： Bodirsky, Manuel Dangelmayr, Cornelia Kára, Jan Department of Algorithms and Complexity Institute for Computer Science Humboldt University Berlin Germany Institute for Mathematics II Free University Berlin Germany Department of Applied Mathematics Faculty of Mathematics and Physics Charles University Prague Czech Republic

In this paper we show that series-parallel graphs (i.e., K 4-minor free graphs) can be represented as contact intersection graphs of straight-line segments in three directions. Moreover, in our representations no two ... 详细信息

ISBN: (纸本)1860948278

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

The Parameterized complexity of Network Microaggregation 37

The Parameterized Complexity of Network Microaggregation

引用

37th AAAI Conference on Artificial Intelligence, AAAI 2023

作者： Blažej, Václav Ganian, Robert Knop, Dušan Pokorný, Jan Schierreich, Šimon Simonov, Kirill Faculty of Information Technology Czech Technical University in Prague Prague Czech Republic Algorithms and Complexity Group Technische Universität Wien Vienna Austria Hasso Plattner Institute University of Potsdam Postdam Germany

ISBN: (纸本)9781577358800

Microaggregation is a classical statistical disclosure control technique which requires the input data to be partitioned into clusters while adhering to specified size constraints. We provide novel exact algorithms and lower bounds for the task of microaggregating a given network while considering both unrestricted and connected clusterings, and analyze these from the perspective of the parameterized complexity paradigm. Altogether, our results assemble a complete complexity-theoretic picture for the network microaggregation problem with respect to the most natural parameterizations of the problem, including input-specified parameters capturing the size and homogeneity of the clusters as well as the treewidth and vertex cover number of the network. Copyright © 2023, Association for the Advancement of Artificial Intelligence (***). All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Estimating Cell Cycle Phase Distribution of Yeast from Time Series Gene Expression Data

Estimating Cell Cycle Phase Distribution of Yeast from Time ...

引用

International Conference on Information and Electronics Engineering（ICIEE 2011）

作者： Jhoirene Clemente Julie Ann Salido Raissa Relator Algorithms and Complexity Laboratory Department of Computer Science Institute of Mathematics University of the Philippines Diliman

Two standard methods for estimating the cell cycle phase distribution of a yeast population are budding index analysis and one that uses fluorescence-activated cell sorter（FACS）.However,both of these methods will require wet lab *** this research,we propose a method that estimates the cell cycle phase distribution from the time series gene expression data.

关键词： Cell cycle phase distribution FACS budding index analysis time series gene expression data spectral clustering kernel k-means clustering.

来源：评论

学校读者我要写书评

暂无评论

Brief announcement: Treewidth modulator: Emergency exit for DFVS 45

Brief announcement: Treewidth modulator: Emergency exit for ...

引用

45th International Colloquium on Automata, Languages, and Programming, ICALP 2018

作者： Lokshtanov, Daniel Ramanujan, M.S. Saurabh, Saket Sharma, Roohani Zehavi, Meirav Department of Informatics University of Bergen Norway Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI UMI ReLax India Department of Computer Science Ben-Gurion University Israel

ISBN: (纸本)9783959770767

In the Directed Feedback Vertex Set (DFVS) problem, we are given as input a directed graph D and an integer k, and the objective is to check whether there exists a set S of at most k vertices such that F = D − S is a directed acyclic graph (DAG). Determining whether DFVS admits a polynomial kernel (parameterized by the solution size) is one of the most important open problems in parameterized complexity. In this article, we give a polynomial kernel for DFVS parameterized by the solution size plus the size of any treewidth-η modulator, for any positive integer η. We also give a polynomial kernel for the problem, which we call Vertex Deletion to treewidth-η DAG, where given as input a directed graph D and a positive integer k, the objective is to decide whether there exists a set of at most k vertices, say S, such that D − S is a DAG and the treewidth1 of D − S is at most η. © 2018 Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. All rights reserved.

关键词： Directed graphs

来源：评论

学校读者我要写书评

暂无评论

Self-stabilising Byzantine clock synchronisation is almost as easy as consensus

Self-stabilising Byzantine clock synchronisation is almost a...

引用

作者： Lenzen, Christoph Rybicki, Joel Department of Algorithms and Complexity Max Planck Institute for Informatics Saarland Informatics Campus Campus E1 4 Saarbrücken66123 Germany Am Campus 1 Klosterneuburg3400 Austria

We give fault-tolerant algorithms for establishing synchrony in distributed systems in which each of the n nodes has its own clock. Our algorithms operate in a very strong fault model: we require self-stabilisation, i.e., the initial state of the system may be arbitrary, and there can be up to f © 2019 Copyright held by the owner/author(s).

关键词： Clocks

来源：评论

学校读者我要写书评

暂无评论

Single machine batch scheduling to minimize the weighted number of tardy Jobs

arXiv

引用

arXiv 2019年

作者： Hermelin, Danny Mnich, Matthias Omlor, Simon Ben-Gurion University of the Negev Beer-Sheva Tu Hamburg Institute for Algorithms and Complexity Hamburg

The 1|B,rj| wjUjscheduling problem takes as input a batch setup time Δ and a set of n jobs, each having a processing time, a release date, a weight, and a due date;the task is to find a sequence of batches that minimizes the weighted number of tardy jobs. This problem was introduced by Hochbaum and Landy in 1994;as a wide generalization of r Knapsack, it is NP-hard. In this work we provide a multivariate complexity analysis of the 1|B, rj| wjUjproblem with respect to several natural parameters. That is, we establish a thorough classifica-tion into fixed-parameter tractable and Wr1s-hard problems, for parameter combinations of (i) #p = distinct number of processing times, (ii) #w = number of distinct weights, (iii) #d = number of distinct due dates, (iv) #r = number of distinct release dates, and (v) b = batch sizes. Thereby, we significantly extend the work of Hermelin et al. (2018) who analyzed the parameterized complexity of the non-batch variant of this problem without r release dates. As one of our key results, we prove that 1|B,rj| wjUjis Wr1s-hard parameterized by the number of distinct processing times and distinct due dates. To the best of our r knowledge, these are the first parameterized intractability results for scheduling problems with few distinct processing times. Further, we show that 1|B, rj| wjUjis fixed-parameter tractable with respect to parameter #p#d#r and with respect to parameter #w#d if there is just a single release date. Both results hold even if the number of jobs per batch is limited by some integer b. Copyright © 2019, The Authors. All rights reserved.

关键词： Parameterization

来源：评论

学校读者我要写书评

暂无评论

Geometric systems of unbiased representatives 31

Geometric systems of unbiased representatives

引用

31st Canadian Conference on Computational Geometry, CCCG 2019

作者： Banik, Aritra Bhattacharya, Bhaswar B. Bhore, Sujoy Martínez-Sandoval, Leonardo National Institute of Science Education and Research School of Computer Sciences HBNI Bhubaneswar India Department of Statistics University of Pennsylvania Philadelphia United States Algorithms and Complexity Group TU Wien Vienna Austria Sorbonne Université France

Let P be a set of points in Rd, B a bicoloring of P and O a family of geometric objects (that is, intervals, boxes, balls, etc). An object from O is called balanced with respect to B if it contains the same number of points from each color of B. For a collection B of bicolorings of P, a geometric system of unbiased representatives (GSUR) is a subset such that for any bicoloring B of β there is an object in O0 that is balanced with respect to B. We study the problem of finding G-SURs. We obtain general bounds on the size of G-SURs consisting of intervals, size-restricted intervals, axis-parallel boxes and Euclidean balls. We show that the G-SUR problem is NP-hard even in the simple case of points on a line and interval ranges. Furthermore, we study a related problem on determining the size of the largest and smallest balanced intervals for points on the real line with a random distribution and coloring. Our results are a natural extension to a geometric context of the work initiated by Balachandran et al. on arbitrary systems of unbiased representatives. © CCCG 2019. All rights reserved.

关键词： Computational geometry

来源：评论

学校读者我要写书评

暂无评论

Hitting weighted even cycles in planar graphs

arXiv

引用

arXiv 2021年

作者： Göke, Alexander Koenemann, Jochen Mnich, Matthias Sun, Hao Hamburg University of Technology Institute for Algorithms and Complexity Hamburg Germany University of Waterloo Waterloo Canada

A classical branch of graph algorithms is graph transversals, where one seeks ¡a minimum-weight subset of nodes in a node-weighted graph G which intersects all copies of subgraphs F from a fixed family F. Many such graph transversal problems have been shown to admit polynomial-time approximation schemes (PTAS) for planar input graphs G, using a variety of techniques like the shifting technique (Baker, J. ACM 1994), bidimensionality (Fomin et al., SODA 2011), or connectivity domination (Cohen-Addad et al., STOC 2016). These techniques do not seem to apply to graph transversals with parity constraints, which have recently received significant attention, but for which no PTASs are known. In the even-cycle transversal (ECT) problem, the goal is to find a minimum-weight hitting set for the set of even cycles in an undirected graph. For ECT, Fiorini et al. (IPCO 2010) showed that the integrality gap of the standard covering LP relaxation is Θ(log n), and that adding sparsity inequalities reduces the integrality gap to 10. Our main result is a primal-dual algorithm that yields a 47/7 ≈ 6.71-approximation for ECT on node-weighted planar graphs, and an integrality gap of the same value for the standard LP relaxation on node-weighted planar *** Codes 68W25 Copyright © 2021, The Authors. All rights reserved.

关键词： Graphic methods

来源：评论

学校读者我要写书评

暂无评论

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

请选择保存的检索档案：

请选择收藏分类：

通借通还

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

时间限定

文献类型

馆藏选择

核心期刊

语言

文献类型

帮助

文字说明：

检索规则说明：

检索范例：

分类表

所选分类

限定检索结果

文献类型

馆藏范围

日期分布

学科分类号

主题

机构

作者

语言

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

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

通借通还

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

请选择保存的检索档案：

请选择收藏分类：