Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 20 of 21 for “"Pathwidth"”.
-
New algorithms for pathwidth computation
The notions of pathwidth and the closely related treewidth have become more and more important recently. The importance lies not only in theory but also in practice. Theoretically, lots of NP-hard problems become polynomially solvable when restricted in graphs with bounded pathwidth (or treewidth). …
-
Stack Number, Track Number, and Layered Pathwidth
… graphs : stack number, track number, and layered pathwidth. Our first result is to show that the stack number of any graph is at most 4 times its layered pathwidth. This result complements an existing result of Dujmovic et al. that showed that the queue number of a graph is at most 3 times its …
-
Balancing Branching and Pathwidth: Threshold-Based Approaches for Exponential Algorithms
… algorithms for NP-hard problems that combine a pathwidth-based approach and a branching approach. In this context, we investigate how a running time analysis can decide thresholds to balance the two methods, thereby improving the running times for such NP-hard problems. We approach this question …
-
On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs
… problem in cactus graphs and graphs of bounded pathwidth. Despite many previous efforts, the complexity of the problem in cactus graphs remained open. We settle this question by establishing the NP-completeness of broadcasting in cactus graphs and graphs of pathwdith 2. On the positive side, we …
-
Cache scheduling
… Scheduling generalizes known problems such as Pathwidth and Gate Matrix Layout. We show that a generalization of Pathwidth, which we call Almost Pathwidth, is a special case of Cache Scheduling and is a graph problem that is closed under taking graph minors.
-
Transversals of Geometric Objects and Anagram-Free Colouring
… in Wilson's thesis and shows that even graphs of pathwidth 2 do not have anagram-free colouring with a bounded number of colours. The third article is a study on the geodesic anagram-free chromatic number of chordal and interval graphs. \emph{Geodesic anagram-free chromatic number} is defined as …
-
Finite state properties of bounded parthwidth graphs
The concepts of the treewidth and pathwidth of combinatorial structures have come to play a central role in a number of important developments in discrete mathematics and combinatorial algorithm design. In particular, they are of fundamental importance to several general algorithm design techniques …
-
Topics in Graph Algorithms: Structural Results and Algorithmic Techniques, with Applications
… We discuss graph metrics such as treewidth and pathwidth. Treewidth is well studied, mainly because many problems that are NP-hard in general have polynomial time algorithms when restricted to graphs of bounded treewidth. Pathwidth has many applications ranging from circuit layout to natural …
-
Algorithmic Methods for circuit layout and partitioning
… metric is optimized. We begin by considering pathwidth. This metric is directly related to the area of circuits laid out in Gate Matrix and Weinberger array styles. It is <em>NP</em>-hard to determine pathwidth, even on severely restricted classes of graphs. We present algorithms to …
-
A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings
… depth to other graph parameters such as the pathwidth and the rooted pathwidth, which have been used in the past for outerplanar graph drawing algorithms.
-
Coloured graph models: Associating emitters and ships
… matchings in related graphs, which have bounded pathwidth. Restricting to graphs with bounded pathwidth is a reasonable simplification, as signals come in along bearings (i.e. along a cycle) and a cycle has pathwidth two. New algorithms to find (weighted) matchings in graphs with bounded …
-
Extending Pappus' Theorem
… above, the matroids $M_1$ and $M_2$ both have pathwidth bounded by some constant depending only on $q$. That result plays a significant role in their announced proof of Rota's Conjecture. Bounding the pathwidth of $M_1$ and $M_2$ is currently the single most complicated part in the proof of …
-
Proofdoors and efficiency of CDCL solvers
… CacheSAT algorithm via clause-variable incidence pathwidth, and show how CDCL can simulate such executions. As an application, we prove that SAT encodings of floating-point addition commutativity admit small proofdoors, explaining their tractability.
-
Sampling and Counting Graph Structures with Triangle Motifs
… mixing time bounds on graphs of bounded pathwidth and degree, with a corollary extending to bounded treewidth. By the sampling-to-counting reduction, this also yields approximate counting algorithms for MDT structures on the same class of graphs. Our analysis highlights the challenges in …
-
Separation and Cover Problems in Temporal Graph
… Separator where the temporal graph has bounded pathwidth. Therefore, solving (s,z,t)-Temporal Separator on temporal graph whose underlying graph has bounded pathwidth is more difficult than solving Discrete Segment Covering problem where all segments' lengths are bounded. Discrete segment cover …
-
Graph colourings and games
… it to be W[1]-hard when parameterised by the pathwidth of the input graph. These results answer two open questions of Fellows, Fomin, Lokshtanov, Rosamond, Saurabh, Szeider and Thomassen.</p>
-
On Token Movement Problems
… discovery variants with respect to the parameter pathwidth. Beyond fixed-parameter tractability, we investigate the kernelization complexity of the studied solution discovery problems to understand the limits of preprocessing. Kernelization provides a mathematical framework for analyzing data …
-
Algorithms for VLSI layout based on graph width metrics
… lower and upper bounds for the treewidth and pathwidth metrics of a graph. We also present fast algorithms to compute some of the bounds in practice. These bounds give us a better understanding of the structure and number of obstruc-tions and we develop a general method to construct some of …
-
Arboreal covers over relational structures
… e.g. treewidth to their path-like variant, e.g. pathwidth.</p> <p> - We show that coKleisli laws of functorial operations over game comonads recover Feferman-Vaught-Mostowski theorems. Feferman-Vaught-Mostowski theorems are a basic tool used to show when a operation that combines structures …
-
Minors of graphs of large path-width
Let P be a graph with a vertex v such that P-v is a forest and let Q be an outerplanar graph. In 1993 Paul Seymour asked if every two-connected graph of sufficiently large path-width contains P or Q as a minor.mDefine g(H) as the minimum number for which there exists a positive integer p(H) such …
Page 1 of 2