1,721,226 research outputs found
Computational Complexity of Norm-Maximization
No full textBodlaender, H.L.; Gritzmann, P.; Klee, V.; Van Leeuwen, J.. (1989). Computational Complexity of Norm-Maximization. Retrieved from the University Digital Conservancy, https://hdl.handle.net/11299/4998
The complexity of graph contractions
Full text linkFor a fixed pattern graph H, let H-CONTRACTIBILITY denote the problem of deciding whether a given input graph is contractible to H. We continue a line of research that was started in 1987 by Brouwer & Veldman, and we determine the computational complexity of H-CONTRACTIBILITY for certain classes of pattern graphs. In particular, we pin-point the complexity for all graphs H with five vertices.
Interestingly, in all cases that are known to be polynomially solvable, the pattern graph H has a dominating vertex, whereas in all cases that are known to be NP-complete, the pattern graph H does not have a dominating vertex
Inefficiency of Standard Multi-unit Auctions
No full textWe study two standard multi-unit auction formats for allocating multiple units of a single good to multi-demand bidders. The first one is the Discriminatory Auction, which charges every winner his winning bids. The second is the Uniform Price Auction, which determines a uniform price to be paid per unit. Variants of both formats find applications ranging from the allocation of state bonds to investors, to online sales over the internet. For these formats, we consider two bidding interfaces: (i) standard bidding, which is most prevalent in the scientific literature, and (ii) uniform bidding, which is more popular in practice. In this work, we evaluate the economic inefficiency of both multi-unit auction formats for both bidding interfaces, by means of upper and lower bounds on the Price of Anarchy for pure Nash equilibria and mixed Bayes-Nash equilibria. Our developments improve significantly upon bounds that have been obtained recently for submodular valuation functions. Also, for the first time, we consider bidders with subadditive valuation functions under these auction formats. Our results signify near-efficiency of these auctions, which provides further justification for their use in practice
Parameterized Complexity of Restricted Variants of Some Classical Problems
No full textAs the title of this thesis suggests, we study how does the complexity of problems change if we add some restrictions to them. In order to achieve this, we use the framework of parameterized complexity. In contrast to classical complexity, where we express the number of steps in terms of input size, in parameterized complexity we express the number of steps in terms of the input size and an extra parameter.
In the first part of the thesis, we study how adding structure to the input makes problems easier. We consider the Subgraph Isomorphism problem on unit disk graphs, and the Set Cover problem where the sets form arithmetic progressions. In the second part of the thesis, we add restrictions on the solution. We start from the Flow problem, and we consider two natural restrictions, namely connectivity and the all-or-nothing restriction
Graph-theoretic concepts in computer science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers
No full textVertex deletion for 3D Delaunay triangulations
No full textWe show how to delete a vertex q from a three-dimensional Delaunay triangulation DT(S) in expected O(C¿¿¿(P)) time, where P is the set of vertices neighboring q in DT(S) and C¿¿¿(P) is an upper bound on the expected number of tetrahedra whose circumspheres enclose q that are created during the randomized incremental construction of DT(P). Experiments show that our approach is significantly faster than existing implementations if q has high degree, and competitive if q has low degree
Parameterized Graph Problems: Counting, the Tutte Polynomial and Logarithmic Space
No full textIn this thesis we study the computational complexity of various parameterized graph problems. The complexity of a problem measures the difficulty of a problem as the amount of time it costs to solve it. A parameterized problem includes some extra measure of the complexity of the instance, referred to as a parameter. Many of the problems we consider are counting problems, which can be thought of as asking for the number of solutions to some problem, rather than just a single solution.
In the first part we study the Tutte polynomial, whose coefficients depend on some given graph. The Tutte polynomial generalizes a number of well known counting problems. We study a number of these in more detail, including graph colorings, connected edgesets and spanning forests. We give a classification of the parameterized complexity of computing the Tutte polynomial on integer points, for the parameters pathwidth, treewidth and cutwidth.
In the second part we discuss the complexity classes XNLP and XALP, as well as introducing the counting variants #XLP and #XALP of these classes. A complexity class can be thought of as a large collection of algorithmic problems, that share some upper bound on their computational complexity. We give complete problems for all four of these classes, which is to say we show for some problems in the classes that they are at least as hard as any other problem in that class
Backbone Colorings for Networks
Full text linkWe introduce and study backbone colorings, a variation on classical vertex colorings: Given a graph G = (V, E) and a spanning subgraph H of G (the backbone of G), a backbone coloring for G and H is a proper vertex coloring V -> {1, 2, ...} of G in which the colors assigned to adjacent vertices in H differ by at least two. We study the cases where the backbone is either a spanning tree or a spanning path. We show that for tree backbones of G..
Labeling moving points with a trade-off between label speed and label overlap
No full textTraditional map-labeling algorithms ensure that the labels being placed do not overlap each other, either by omitting labels or scaling them. This is undesirable in applications where the points to be labeled are moving. We develop and experimentally evaluate a heuristic for labeling moving points. Our algorithm labels all the points with labels of a fixed size, while trying to minimize the number of overlapping labels and ensuring smoothly moving labels. It allows a trade-off between label speed and label overlap
Graph-theoretic concepts in computer science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers
No full text- …
