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

Parameterized algorithms for book embedding problems

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bhore, Sujoy Ganian, Robert Montecchiani, Fabrizio Nöllenburg, Martin Algorithms and Complexity Group TU Wien Vienna Austria Engineering Department University of Perugia Perugia Italy

A k-page book embedding of a graph G draws the vertices of G on a line and the edges on k half-planes (called pages) bounded by this line, such that no two edges on the same page cross. We study the problem of determining whether G admits a k-page book embedding both when the linear order of the vertices is fixed, called Fixed-Order Book Thickness, or not fixed, called Book Thickness. Both problems are known to be NP-complete in general. We show that Fixed-Order Book Thickness and Book Thickness are fixed-parameter tractable parameterized by the vertex cover number of the graph and that Fixed-Order Book Thickness is fixed-parameter tractable parameterized by the pathwidth of the vertex order. Copyright © 2019, The Authors. All rights reserved.

关键词： Parameterization

Algorithm and hardness results on liar’s dominating set and k-tuple dominating set

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Banerjee, Sandip Bhore, Sujoy Department of Computer Science Hebrew University of Jerusalem Israel Algorithms and Complexity Group Technische Universität Wien Austria

Given a graph G = (V, E), the dominating set problem asks for a minimum subset of vertices D ⊆ V such that every vertex u ∈ V \D is adjacent to at least one vertex v ∈ D. That is, the set D satisfies the condition that |N[v] ∩ D| ≥ 1 for each v ∈ V , where N[v] is the closed neighborhood of v. In this paper, we study two variants of the classical dominating set problem: k-tuple dominating set (k-DS) problem and Liar’s dominating set (LDS) problem, and obtain several algorithmic and hardness results. On the algorithmic side, we present a constant factor (112 )-approximation algorithm for the Liar’s dominating set problem on unit disk graphs. Then, we obtain a PTAS for the k-tuple dominating set problem on unit disk graphs. On the hardness side, we show a Ω(n2) bits lower bound for the space complexity of any (randomized) streaming algorithm for Liar’s dominating set problem as well as for the k-tuple dominating set problem. Furthermore, we prove that the Liar’s dominating set problem on bipartite graphs is W[2]-hard. Copyright © 2019, The Authors. All rights reserved.

关键词： Graph theory

On layered fan-planar graph drawings

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Biedl, Therese Chaplick, Steven Fiala, Jiři Kaufmann, Michael Montecchiani, Fabrizio Nöllenburg, Martin Raftopoulou, Chrysanthi University of Waterloo Canada Universität Würzburg Germany Charles University Prague Czech Republic Universität Tübingen Germany Università degli Studi di Perugia Italy Algorithms and Complexity Group TU Wien Vienna Austria National Technical University of Athens Greece

In this paper, we study fan-planar drawings that use h layers and are proper, i.e., edges connect adjacent layers. We show that if the embedding of the graph is fixed, then testing the existence of such drawings is fixed-parameter tractable in h, via a reduction to a similar result for planar graphs by Dujmović et al. If the embedding is not fixed, then we give partial results for h = 2: It was already known how to test existence of fan-planar proper 2-layer drawings for 2-connected graphs, and we show here how to test this for trees. Along the way, we exhibit other interesting results for graphs with a fan-planar proper hlayer drawing;in particular we bound their pathwidth and show that they have a bar-1-visibility representation. Copyright © 2020, The Authors. All rights reserved.

关键词： Embeddings

Integer programming and incidence treedepth

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Eiben, Eduard Ganian, Robert Knop, Dušan Ordyniak, Sebastian Pilipczuk, Michal Wrochna, Marcin Department of Computer Science Royal Holloway University of London United Kingdom Algorithms and Complexity Group Vienna University of Technology Austria Department of Theoretical Computer Science Czech Technical University in Prague Czech Republic School of Computing University of Leeds United Kingdom Institute of Informatics University of Warsaw Poland University of Oxford United Kingdom

Recently a strong connection has been shown between the tractability of integer programming (IP) with bounded coefficients on the one side and the structure of its constraint matrix on the other side. To that end, integer linear programming is fixed-parameter tractable with respect to the primal (or dual) treedepth of the Gaifman graph of its constraint matrix and the largest coefficient (in absolute value). Motivated by this, Koutecký, Levin, and Onn [ICALP 2018] asked whether it is possible to extend these result to a more broader class of integer linear programs. More formally, is integer linear programming fixed-parameter tractable with respect to the incidence treedepth of its constraint matrix and the largest coefficient (in absolute value)? We answer this question in negative. In particular, we prove that deciding the feasibility of a system in the standard form, Ax = b, l 6 x 6 u, is NP-hard even when the absolute value of any coefficient in A is 1 and the incidence treedepth of A is 5. Consequently, it is not possible to decide feasibility in polynomial time even if both the assumed parameters are constant, unless P = NP. Moreover, we complement this intractability result by showing tractability for natural and only slightly more restrictive settings, namely: (1) treedepth with an additional bound on either the maximum arity of constraints or the maximum number of occurrences of variables and (2) the vertex cover number. Copyright © 2020, The Authors. All rights reserved.

关键词： Integer programming

Geometric systems of unbiased representatives

学校读者我要写书评

暂无评论

arXiv 2020年

作者： Banik, Aritra Bhattacharya, Bhaswar B. Bhore, Sujoy Martínez-Sandoval, Leonardo School of Computer Sciences National Institute of Science Education and Research HBNI Bhubaneswar India Department of Statistics University of Pennsylvania Philadelphia United States Algorithms and Complexity Group Technische Universität Wien Austria Institut de Mathématiques de Jussieu-Paris Rive Gauche UMR 7586 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 (G-SUR) is a subset O0 ⊆ O such that for any bicoloring B of B 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. Copyright © 2020, The Authors. All rights reserved.

关键词：

Balanced connected subgraph problem in geometric intersection graphs

学校读者我要写书评

暂无评论

arXiv 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 Gandhinagar Gujarat India

We study the Balanced Connected Subgraph (shortly, BCS) problem on geometric intersection graphs such as interval, circular-arc, permutation, unit-disk, outer-string graphs, etc. Given a vertex-colored graph G = (V, E), where each vertex in V is colored with either "red" or "blue", the BCS problem seeks a maximum cardinality induced connected subgraph H of G such that H is color-balanced, 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 algorithm for the Steiner Tree problem on both the interval graphs and circular arc graphs, that is used as a subroutine for solving BCS problem on same graph classes. Finally, we present a FPT algorithm for the BCS problem on general graphs. Copyright © 2019, The Authors. All rights reserved.

关键词： Trees (mathematics)

Perfect Pseudo-Matchings in cubic graphs

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Fleischner, Herbert Behrooz Bagheri, Gh. Klocker, Benedikt Algorithms and Complexity Group Vienna University of Technology Favoritenstrasse 9-11 Vienna1040 Department of Mathematics West Virginia University MorgantownWV26506-6310 United States

A perfect pseudo-matching M in a cubic graph G is a spanning subgraph of G such that every component of M is isomorphic to K2or to K1,3. In view of snarks G with dominating cycle C, this is a natural generalization of perfect matchings since G\E(C) is a perfect pseudo-matching. Of special interest are such M where G/M is planar because such G have a cycle double cover. We show that various well known classes of snarks contain planarizing perfect pseudo-matchings, and that there are at least as many snarks with planarizing perfect pseudo-matchings as there are cyclically 5-edge-connected *** Codes 05C45, 05C10, 05C60 Copyright © 2019, The Authors. All rights reserved.

关键词： Graph theory

External labeling techniques: A taxonomy and survey

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bekos, Michael A. Niedermann, Benjamin Nöllenburg, Martin Institute for Informatics University of Tübingen Tübingen Germany Institute of Geodesy and Geoinformation University of Bonn Bonn Germany Algorithms and Complexity Group Tu Wien Vienna Austria

External labeling is frequently used for annotating features in graphical displays and visualizations, such as technical illustrations, anatomical drawings, or maps, with textual information. Such a labeling connects features within an illustration by thin leader lines with their labels, which are placed in the empty space surrounding the image. Over the last twenty years, a large body of literature in diverse areas of computer science has been published that investigates many different aspects, models, and algorithms for automatically placing external labels for a given set of features. This state-of-the-art report introduces a first unified taxonomy for categorizing the different results in the literature and then presents a comprehensive survey of the state of the art, a sketch of the most relevant algorithmic techniques for external labeling algorithms, as well as a list of open research challenges in this multidisciplinary research field. Copyright © 2019, The Authors. All rights reserved.

关键词： Taxonomies

Scheduling with non-renewable resources: Minimizing the sum of completion times

学校读者我要写书评

暂无评论

arXiv 2019年

作者： Bércziy, Kristóf Királyz, Tamás Omlorx, Simon MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Tu Hamburg Institute for Algorithms and Complexity Hamburg

The paper considers single-machine scheduling problems with a non-renewable resource. In this setting, we are given a set jobs, each of which is characterized by a processing time, a weight, and the job also has some resource requirement. At fixed points in time, a certain amount of the resource is made available to be consumed by the jobs. The goal is to assign the jobs non-preemptively to time slots on the machine, so that at any time their resource requirement does not exceed the available amounts of resources. The objective that we consider here is the minimization of the sum of weighted completion times. We give polynomial approximation algorithms and complexity results for single scheduling machine problems. In particular, we show strong NP-hardness of the case of unit resource requirements and weights (1|rm = 1, aj= 1| £ Cj), thus answering an open question of Györgyi and Kis. We also prove that the schedule corresponding to the Shortest Processing Time First ordering provides a 3/2-approximation for the same problem. We give simple constant factor approximations and a more complicated PTAS for the case of 0 processing times (1|rm = 1,pj= 0wjCj). We close the paper by proposing a new variant of the problem in which the resource arrival times are unknown. A 4-approximation is presented for this variant, together with an (4 - ϵ)-inapproximability result. Copyright © 2019, The Authors. All rights reserved.

关键词： Approximation algorithms