Results 101 to 110 of about 5,081 (203)
The frequency assignment problem [PDF]
, 2004 This thesis was submitted for the degree of Doctor of Philosophy and awarded by Brunel University.This thesis examines a wide collection of frequency assignment problems.
Koller, Angela Erika
core +2 more sources
On the parameterized complexity of computing tree-partitions [PDF]
Discrete Mathematics & Theoretical Computer ScienceWe study the parameterized complexity of computing the tree-partition-width, a graph parameter equivalent to treewidth on graphs of bounded maximum degree.
Hans L. Bodlaender +2 more
doaj +1 more source
Approximating the Treewidth of AT-Free Graphs
Discrete Applied Mathematics, 2000 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Bouchitté, Vincent, Todinca, Ioan
openaire +4 more sources
On the tree-width of knot diagrams
Journal of Computational Geometry, 2019 We show that a small tree-decomposition of a knot diagram induces a small sphere-decomposition of the corresponding knot. This, in turn, implies that the knot admits a small essential planar meridional surface or a small bridge sphere.
Saul Schleimer +3 more
doaj +1 more source
The treewidth and pathwidth of hypercubes
Discrete Mathematics, 2006 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
L. Sunil Chandran, Telikepalli Kavitha
openaire +1 more source
On the Complexity of Embedding in Graph Products
Computing in Geometry and TopologyGraph embedding, especially as a subgraph of a grid, is an old topic in VLSI design and graph drawing. In this paper, we investigate related questions concerning the complexity of embedding a graph G in a host graph that is the strong product of a path ...
Therese Biedl +2 more
doaj +1 more source
The algorithmic theory of treewidth
Electronic Notes in Discrete Mathematics, 2000 Abstract Treewidth is a graph measure with several applications. In this abstract, it is discussed that many otherwise intractable problems become polynomial or linear time solvable when restricted to graphs of bounded treewidth, and some other algorithmic results that use treewidth (e.g., applied to planar graphs) are discussed.
openaire +1 more source
Contraction obstructions for treewidth
Journal of Combinatorial Theory, Series B, 2011 zbMATH Open Web Interface contents unavailable due to conflicting licenses.
Fedor V. Fomin +2 more
openaire +3 more sources
Automated design of dynamic programming schemes for RNA folding with pseudoknots. [PDF]
Algorithms Mol Biol, 2023 Marchand B +4 more
europepmc +1 more source
CoRR, 2019 We characterise digraphs of directed treewidth one in terms of forbidden butterfly minors. Moreover, we show that there is a linear relation between the hypertree-width of the dual of the cycle hypergraph of D, i. e. the hypergraph with vertices V (D) where every hyperedge corresponds to a directed cycle in D, and the directed treewidth of D.
openaire +2 more sources