05 Fakultät Informatik, Elektrotechnik und Informationstechnik

Permanent URI for this collectionhttps://elib.uni-stuttgart.de/handle/11682/6

Browse

Institute: search.filters.UBSInstitut.Institut für Formale Methoden der InformatikPublication Type: search.filters.UBSTyp.Zeitschriftenartikel

Search Results

Now showing 1 - 7 of 7
  • Thumbnail Image
    ItemOpen Access
    A lower bound for the query phase of contraction hierarchies and hub labels and a provably optimal instance-based schema
    (2021) Rupp, Tobias; Funke, Stefan
    We prove a Ω(√n) lower bound on the query time for contraction hierarchies (CH) as well as hub labels, two popular speed-up techniques for shortest path routing. Our construction is based on a graph family not too far from subgraphs that occur in real-world road networks, in particular, it is planar and has a bounded degree. Additionally, we borrow ideas from our lower bound proof to come up with instance-based lower bounds for concrete road network instances of moderate size, reaching up to 96% of an upper bound given by a constructed CH. For a variant of our instance-based schema applied to some special graph classes, we can even show matching upper and lower bounds.
  • Thumbnail Image
    ItemOpen Access
    Equation satisfiability in solvable groups
    (2022) Idziak, Paweł; Kawałek, Piotr; Krzaczkowski, Jacek; Weiß, Armin
    The study of the complexity of the equation satisfiability problem in finite groups had been initiated by Goldmann and Russell in (Inf. Comput. 178 (1), 253-262, 10 ) where they showed that this problem is in P for nilpotent groups while it is NP -complete for non-solvable groups. Since then, several results have appeared showing that the problem can be solved in polynomial time in certain solvable groups G having a nilpotent normal subgroup H with nilpotent factor G / H . This paper shows that such a normal subgroup must exist in each finite group with equation satisfiability solvable in polynomial time, unless the Exponential Time Hypothesis fails.
  • Thumbnail Image
    ItemOpen Access
    Sublinear search spaces for shortest path planning in grid and road networks
    (2021) Blum, Johannes; Funke, Stefan; Storandt, Sabine
    Shortest path planning is a fundamental building block in many applications. Hence developing efficient methods for computing shortest paths in, e.g., road or grid networks is an important challenge. The most successful techniques for fast query answering rely on preprocessing. However, for many of these techniques it is not fully understood why they perform so remarkably well, and theoretical justification for the empirical results is missing. An attempt to explain the excellent practical performance of preprocessing based techniques on road networks (as transit nodes, hub labels, or contraction hierarchies) in a sound theoretical way are parametrized analyses, e.g., considering the highway dimension or skeleton dimension of a graph. Still, these parameters may be large in case the network contains grid-like substructures - which inarguably is the case for real-world road networks around the globe. In this paper, we use the very intuitive notion of bounded growth graphs to describe road networks and also grid graphs. We show that this model suffices to prove sublinear search spaces for the three above mentioned state-of-the-art shortest path planning techniques. Furthermore, our preprocessing methods are close to the ones used in practice and only require expected polynomial time.
  • Thumbnail Image
    ItemOpen Access
    On the average case of MergeInsertion
    (2020) Stober, Florian; Weiß, Armin
    MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting algorithm which, up to today, for many input sizes achieves the best known upper bound on the number of comparisons. Indeed, it gets extremely close to the information-theoretic lower bound. While the worst-case behavior is well understood, only little is known about the average case. This work takes a closer look at the average case behavior. In particular, we establish an upper bound of nlogn-1.4005n+o(n) comparisons. We also give an exact description of the probability distribution of the length of the chain a given element is inserted into and use it to approximate the average number of comparisons numerically. Moreover, we compute the exact average number of comparisons for n up to 148. Furthermore, we experimentally explore the impact of different decision trees for binary insertion. To conclude, we conduct experiments showing that a slightly different insertion order leads to a better average case and we compare the algorithm to Manacher’s combination of merging and MergeInsertion as well as to the recent combined algorithm with (1,2)-Insertionsort by Iwama and Teruyama.
  • Thumbnail Image
    ItemOpen Access
    Properties of graphs specified by a regular language
    (2022) Diekert, Volker; Fernau, Henning; Wolf, Petra
    Traditionally, graph algorithms get a single graph as input, and then they should decide if this graph satisfies a certain property  Φ. What happens if this question is modified in a way that we get a possibly infinite family of graphs as an input, and the question is if there is a graph satisfying  Φin the family? We approach this question by using formal languages for specifying families of graphs, in particular by regular sets of words. We show that certain graph properties can be decided by studying the syntactic monoid of the specification language  L if a certain torsion condition is satisfied. This condition holds trivially if L is regular. More specifically, we use a natural binary encoding of finite graphs over a binary alphabet Σ, and we define a regular set G⊆Σ∗such that every nonempty word w∈Gdefines a finite and nonempty graph. Also, graph properties can then be syntactically defined as languages over Σ. Then, we ask whether the automaton Aspecifies some graph satisfying a certain property  Φ. Our structural results show that we can answer this question for all “typical” graph properties. In order to show our results, we split L into a finite union of subsets and every subset of this union defines in a natural way a single finite graph F where some edges and vertices are marked. The marked graph in turn defines an infinite graph  F∞and therefore the family of finite subgraphs of F∞where F appears as an induced subgraph. This yields a geometric description of all graphs specified by  L based on splitting L into finitely many pieces; then using the notion of graph retraction, we obtain an easily understandable description of the graphs in each piece.
  • Thumbnail Image
    ItemOpen Access
    Parallel algorithms for power circuits and the word problem of the Baumslag group
    (2023) Mattes, Caroline; Weiß, Armin
    Power circuits have been introduced in 2012 by Myasnikov, Ushakov and Won as a data structure for non-elementarily compressed integers supporting the arithmetic operations addition and (x,y)↦x·2y. The same authors applied power circuits to give a polynomial time solution to the word problem of the Baumslag group, which has a non-elementary Dehn function. In this work, we examine power circuits and the word problem of the Baumslag group under parallel complexity aspects. In particular, we establish that the word problem of the Baumslag group can be solved in NC -even though one of the essential steps is to compare two integers given by power circuits and this, in general, is shown to be P -complete. The key observation is that the depth of the occurring power circuits is logarithmic and such power circuits can be compared in NC .
  • Thumbnail Image
    ItemOpen Access
    The power word problem in graph products
    (2024) Lohrey, Markus; Stober, Florian; Weiß, Armin
    The power word problem for a group Gasks whether an expression u1x1⋯unxn, where the uiare words over a finite set of generators of Gand the xibinary encoded integers, is equal to the identity of G. It is a restriction of the compressed word problem, where the input word is represented by a straight-line program (i.e., an algebraic circuit over G). We start by showing some easy results concerning the power word problem. In particular, the power word problem for a group Gis uNC1-many-one reducible to the power word problem for a finite-index subgroup of G. For our main result, we consider graph products of groups that do not have elements of order two. We show that the power word problem in a fixed such graph product is AC0-Turing-reducible to the word problem for the free group F2and the power word problems of the base groups. Furthermore, we look into the uniform power word problem in a graph product, where the dependence graph and the base groups are part of the input. Given a class of finitely generated groups Cwithout order two elements, the uniform power word problem in a graph product can be solved in AC0[C=LUPowWP(C)], where UPowWP(C)denotes the uniform power word problem for groups from the class C. As a consequence of our results, the uniform knapsack problem in right-angled Artin groups is NP-complete. The present paper is a combination of the two conference papers (Lohrey and Weiß 2019b, Stober and Weiß 2022a). In Stober and Weiß (2022a) our results on graph products were wrongly stated without the additional assumption that the base groups do not have elements of order two. In the present work we correct this mistake. While we strongly conjecture that the result as stated in Stober and Weiß (2022a) is true, our proof relies on this additional assumption.