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

Parameterized study of steiner tree on unit disk graphs 17

学校读者我要写书评

暂无评论

Parameterized study of steiner tree on unit disk graphs

17th Scandinavian Symposium and Workshops on Algorithm Theory, SWAT 2020

作者： Bhore, Sujoy Carmi, Paz Kolay, Sudeshna Zehavi, Meirav Algorithms and Complexity Group TU Wien Austria Ben-Gurion University of the Negev Beersheba Israel Indian Institute of Technology Kharagpur India

ISBN: (纸本)9783959771504

We study the Steiner Tree problem on unit disk graphs. Given a n vertex unit disk graph G, a subset R ⊆ V(G) of t vertices and a positive integer k, the objective is to decide if there exists a tree T in G that spans over all vertices of R and uses at most k vertices from V \R. The vertices of R are referred to as terminals and the vertices of V(G) \R as Steiner vertices. First, we show that the problem is NP-hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in nO(√t+k) time. We also show that the Steiner Tree problem on unit disk graphs parameterized by k has an FPT algorithm with running time 2O(k)nO(1). In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs [16]. We mention that the algorithmic results can be made to work for Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that Steiner Tree on disk graphs parameterized by k is W[1]-hard. © Sujoy Bhore, Paz Carmi, Sudeshna Kolay, and Meirav Zehavi;licensed under Creative Commons License CC-BY

关键词： Aspect ratio

Worbel: Aggregating point labels into word clouds

学校读者我要写书评

暂无评论

arXiv 2021年

作者： Bhore, Sujoy Ganian, Robert Li, Guangping Nöllenburg, Martin Wulms, Jules Indian Institute of Science Education and Research Bhopal India Algorithms and Complexity Group TU Wien Vienna Austria

Point feature labeling is a classical problem in cartography and GIS that has been extensively studied for geospatial point data. At the same time, word clouds are a popular visualization tool to show the most important words in text data which has also been extended to visualize geospatial data (Buchin et al. PacificVis 2016). In this paper, we study a hybrid visualization, which combines aspects of word clouds and point labeling. In the considered setting, the input data consists of a set of points grouped into categories and our aim is to place multiple disjoint and axis-aligned rectangles, each representing a category, such that they cover points of (mostly) the same category under some natural quality constraints. In our visualization, we then place category names inside the computed rectangles to produce a labeling of the covered points which summarizes the predominant categories globally (in a word-cloud-like fashion) while locally avoiding excessive misrepresentation of points (i.e., retaining the precision of point labeling). We show that computing a minimum set of such rectangles is NP-hard. Hence, we turn our attention to developing heuristics and exact SAT models to compute our visualizations. We evaluate our algorithms quantitatively, measuring running time and quality of the produced solutions, on several artificial and real-world data sets. Our experiments show that the heuristics produce solutions of comparable quality to the SAT models while running much faster. © 2021, CC BY.

关键词： Visualization

Longest Cycle above Erdos–Gallai Bound

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Simonov, Kirill Sagunov, Danil Department of Informatics University of Bergen Norway St. Petersburg Department of V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria

In 1959, Erdos and Gallai proved that every graph G with average vertex degree ad(G) ≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k ≥ 0 in time 2O(k) · nO(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G) + k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own. © 2022, CC BY.

关键词： Graph theory

Circumference of essentially 4-connected planar triangulations

学校读者我要写书评

暂无评论

Journal of Graph algorithms and Applications 2021年第1期25卷 121-132页

作者： Fabrici, Igor Harant, Jochen Mohr, Samuel Schmidt, Jens M. Institute of Mathematics P.J. Šafárik University in Košice Slovakia Institute of Mathematics Ilmenau University of Technology Germany Hamburg University of Technology Institute for Algorithms and Complexity Germany

A 3-connected graph G is essentially 4-connected if, for any 3-cut S ⊆ V (G) of G, at most one component of G − S contains at least two vertices. We prove that every essentially 4-connected maximal planar graph G on n... 详细信息

关键词： Triangulation

Approximation algorithms for coupled task scheduling minimizing the sum of completion times

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fischer, David Györgyi, Péter Institute of Algorithms and Complexity Hamburg University of Technology Blohmstraße 15 Hamburg21079 Germany Institute for Computer Science and Control Eötvös Loránd Research Network Kende Str. 13-17. Budapest1111 Hungary

In this paper we consider the coupled task scheduling problem with exact delay times on a single machine with the objective of minimizing the total completion time of the jobs. We provide constant-factor approximation algorithms for several variants of this problem that are known to be NP-hard, while also proving NP-hardness for two variants whose complexity was unknown before. Using these results, together with constant-factor approximations for the makespan objective from the literature, we also introduce the first results on bi-objective approximation in the coupled task *** Codes 90B35 © 2022, CC BY.

关键词： Approximation algorithms

Detours in Directed Graphs

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Fomin, Fedor V. Golovach, Petr A. Lochet, William Sagunov, Danil Simonov, Kirill Saurabh, Saket Department of Informatics University of Bergen Norway St. Petersburg Department V.A. Steklov Institute of Mathematics Russia JetBrains Research Saint Petersburg Russia Algorithms and Complexity Group TU Wien Austria Institute of Mathematical Sciences HBNI Chennai India

We study two "above guarantee" versions of the classical Longest Path problem on undirected and directed graphs and obtain the following results. In the first variant of Longest Path that we study, called Longest Detour, the task is to decide whether a graph has an (s, t)-path of length at least distG(s, t) + k (where distG(s, t) denotes the length of a shortest path from s to t). Bezáková et al. [7] proved that on undirected graphs the problem is fixed-parameter tractable (FPT) by providing an algorithm of running time 2O(k) · n. Further, they left the parameterized complexity of the problem on directed graphs open. Our first main result establishes a connection between Longest Detour on directed graphs and 3-Disjoint Paths on directed graphs. Using these new insights, we design a 2O(k) · nO(1) time algorithm for the problem on directed planar graphs. Further, the new approach yields a significantly faster FPT algorithm on undirected graphs. In the second variant of Longest Path, namely Longest Path above Diameter, the task is to decide whether the graph has a path of length at least diam(G)+k (diam(G) denotes the length of a longest shortest path in a graph G). We obtain dichotomy results about Longest Path above Diameter on undirected and directed graphs. For (un)directed graphs, Longest Path above Diameter is NP-complete even for k = 1. However, if the input undirected graph is 2-connected, then the problem is FPT. On the other hand, for 2-connected directed graphs, we show that Longest Path above Diameter is solvable in polynomial time for each k ∈ {1, . . ., 4} and is NP-complete for every k ≥ 5. The parameterized complexity of Longest Detour on general directed graphs remains an interesting open problem. © 2022, CC BY.

关键词： Directed graphs

Finding a battleship of uncertain shape

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Hainzl, Eva-Maria Löffler, Maarten Perz, Daniel Tkadlec, Josef Wallinger, Markus Institute of Discrete Mathematics and Geometry TU Wien Austria Department of Computing and Information Sciences Utrecht University Netherlands Institute of Software Technology TU Graz Austria Department of Mathematics Harvard University United States Algorithms and Complexity Group TU Wien Austria

Motivated by a game of Battleship, we consider the problem of efficiently hitting a ship of an uncertain shape within a large playing board. Formally, we fix a dimension d ϵ {1, 2}. A ship is a subset of d. Given a family F of ships, we say that an infinite subset X ⊂ dof the cells pierces F, if it intersects each translate of each ship in F (by a vector in d). In this work, we study the lowest possible (asymptotic) density π(F) of such a piercing subset. To our knowledge, this problem has previously been studied only in the special case |F| = 1 (a single ship). As our main contribution, we present a formula for π(F) when F consists of 2 ships of size 2 each, and we identify the toughest families in several other cases. We also implement an algorithm for finding π(F) in 1D. © 2022, CC BY.

关键词： Ships

Tight complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results

学校读者我要写书评

暂无评论

arXiv 2022年

作者： Focke, Jacob Marx, Dániel Mc Inerney, Fionn Neuen, Daniel Sankar, Govind S. Schepper, Philipp Wellnitz, Philip CISPA Helmholtz Center for Information Security Germany Algorithms and Complexity Group TU Wien Austria School of Computing Science Simon Fraser University Canada Duke University United States Max Planck Institute for Informatics SIC Germany

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets σ, ρ of non-negative integers, a (σ, ρ)-set of a graph G is a set S of vertices such that |N(u) ∩S| ∈ σ for every u ∈ S, and |N(v) ∩S| ∈ ρ for every v ∉ S. The problem of finding a (σ, ρ)-set (of a certain size) unifies standard problems such as Independent Set, Dominating Set, Independent Dominating Set, and many others. For all pairs of finite or cofinite sets (σ, ρ), we determine (under standard complexity assumptions) the best possible value cσ,ρ such that there is an algorithm that counts (σ, ρ)sets in time ctwσ,ρ · nO(1) (if a tree decomposition of width tw is given in the input). Let stop denote the largest element of σ if σ is finite, or the largest missing integer +1 if σ is cofinite;rtop is defined analogously for ρ. Surprisingly, cσ,ρ is often significantly smaller than the natural bound stop + rtop + 2 achieved by existing algorithms [van Rooij, 2020]. Toward defining cσ,ρ, we say that (σ, ρ) is m-structured if there is a pair (α, β) such that every integer in σ equals α mod m, and every integer in ρ equals β mod m. Then, setting • cσ,ρ = stop + rtop + 2 if (σ, ρ) is not m-structured for any m ≥ 2, • cσ,ρ = max{stop, rtop}+ 2 if (σ, ρ) is 2-structured, but not m-structured for any m ≥ 3, and stop = rtop is even, and • cσ,ρ = max{stop, rtop} + 1, otherwise, we provide algorithms counting (σ, ρ)-sets in time ctwσ,ρ · nO(1). For example, for the Exact Independent Dominating Set problem (also known as Perfect Code) corresponding to σ = algorithms and ρ = algorithms, this improves the 3tw · nO(1) algorithm of van Rooij to 2tw · nO(1). Despite the unusually delicate definition of cσ,ρ, an accompanying paper shows that our algorithms are most likely optimal, that is, for any pair (σ, ρ) of finite or cofinite sets where the problem is non-trivial, and any Ε > 0, a (cσ,ρ−Ε)tw ·nO(1)-algorithm counting the number of (σ, ρ)-sets would violate the C

关键词： Trees (mathematics)

Envy-free dynamic pricing schemes

学校读者我要写书评

暂无评论

arXiv 2023年

作者： Bérczi, Kristóf Codazzi, Laura Golak, Julian Grigoriev, Alexander MTA-ELTE Momentum Matroid Optimization Research Group MTA-ELTE Egerváry Research Group Department of Operations Research Eötvös Loránd University Budapest Hungary Institute of Algorithms and Complexity Hamburg University of Technology Hamburg Germany Department of Data Analytics and Digitalisation Maastricht University Maastricht Netherlands

A combinatorial market consists of a set of indivisible items and a set of agents, where each agent has a valuation function that specifies for each subset of items its value for the given agent. From an optimization point of view, the goal is usually to determine a pair of pricing and allocation of the items that provides an efficient distribution of the resources, i.e., maximizes the social welfare, or is as profitable as possible for the seller, i.e., maximizes the revenue. To overcome the weaknesses of mechanisms operating with static prices, a recent line of research has concentrated on dynamic pricing schemes. In this model, agents arrive in an unspecified sequential order, and the prices can be updated between two agent-arrivals. Though the dynamic setting is capable of maximizing social welfare in various scenarios, the assumption that the agents arrive one after the other eliminates the standard concept of fairness. In this paper, we study the existence of optimal dynamic prices under fairness constraints in unit-demand markets. We propose four possible notions of envy-freeness of different strength depending on the time period over which agents compare themselves to others: the entire time horizon, only the past, only the future, or only the present. For social welfare maximization, while the first definition leads to Walrasian equilibria, we give polynomial-time algorithms that always find envy-free optimal dynamic prices in the remaining three cases. In contrast, for revenue maximization, we show that the corresponding problems are APX-hard if the ordering of the agents is fixed. On the positive side, we give polynomial-time algorithms for the setting when the seller can choose the order in which agents arrive. © 2023, CC BY.

关键词： Polynomial approximation