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"”.

  1. 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). …

    rice Repository record for New algorithms for pathwidth computation (opens in a new tab)

  2. 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 …

    ottawa-retro Repository record for Stack Number, Track Number, and Layered Pathwidth (opens in a new tab)

  3. 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 …

    unsw Repository record for Balancing Branching and Pathwidth: Threshold-Based Approaches for Exponential Algorithms (opens in a new tab)

  4. 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 …

    york Repository record for On the Complexity of Telephone Broadcasting: From Cacti to Bounded Pathwidth Graphs (opens in a new tab)

  5. 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.

    uvic Repository record for Cache scheduling (opens in a new tab)

  6. 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 …

    ottawa-retro Repository record for Transversals of Geometric Objects and Anagram-Free Colouring (opens in a new tab)

  7. 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 …

    uvic Repository record for Finite state properties of bounded parthwidth graphs (opens in a new tab)

  8. 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 …

    utk-theses Repository record for Topics in Graph Algorithms: Structural Results and Algorithmic Techniques, with Applications (opens in a new tab)

  9. 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 …

    utk-theses Repository record for Algorithmic Methods for circuit layout and partitioning (opens in a new tab)

  10. 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.

    waterloo Repository record for A 2-Approximation for the Height of Maximal Outerplanar Graph Drawings (opens in a new tab)

  11. 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 …

    oxford Repository record for Coloured graph models: Associating emitters and ships (opens in a new tab)

  12. 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 …

    waterloo Repository record for Extending Pappus' Theorem (opens in a new tab)

  13. 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.

    gatech Repository record for Proofdoors and efficiency of CDCL solvers (opens in a new tab)

  14. 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 …

    rit Repository record for Sampling and Counting Graph Structures with Triangle Motifs (opens in a new tab)

  15. 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 …

    concordia Download PDF for Separation and Cover Problems in Temporal Graph (opens in a new tab)

  16. 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>

    oxford Repository record for Graph colourings and games (opens in a new tab)

  17. 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 …

    waterloo Repository record for On Token Movement Problems (opens in a new tab)

  18. 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 …

    utk-theses Repository record for Algorithms for VLSI layout based on graph width metrics (opens in a new tab)

  19. 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 …

    oxford Repository record for Arboreal covers over relational structures (opens in a new tab)

  20. 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 …

    gatech Repository record for Minors of graphs of large path-width (opens in a new tab)

Page 1 of 2