Results 71 to 80 of about 2,730 (147)
The Effect of Planarization on Width
, 2017 We study the effects of planarization (the construction of a planar diagram $D$ from a non-planar graph $G$ by replacing each crossing by a new vertex) on graph width parameters.
DG Corneil +14 more
core +1 more source
A 3-approximation for the pathwidth of Halin graphs
Journal of Discrete Algorithms, 2004 AbstractWe prove that the pathwidth of Halin graphs can be 3-approximated in linear time. Our approximation algorithms is based on a combinatorial result about respectful edge orderings of trees. Using this result we prove that the linear width of Halin graph is always at most three times the linear width of its skeleton.
Dimitrios M. Thilikos, Fedor V. Fomin
openaire +3 more sources
A linear fixed parameter tractable algorithm for connected pathwidth [PDF]
arXiv, 2020 The graph parameter of pathwidth can be seen as a measure of the topological resemblance of a graph to a path. A popular definition of pathwidth is given in terms of node search where we are given a system of tunnels that is contaminated by some infectious substance and we are looking for a search strategy that, at each step, either places a searcher ...
arxiv
Partitions and Coverings of Trees by Bounded-Degree Subtrees [PDF]
, 2010 This paper addresses the following questions for a given tree $T$ and integer $d\geq2$: (1) What is the minimum number of degree-$d$ subtrees that partition $E(T)$? (2) What is the minimum number of degree-$d$ subtrees that cover $E(T)$?
Wood, David R.
core
Anagram-Free Chromatic Number is not Pathwidth-Bounded [PDF]
arXiv, 2018 The anagram-free chromatic number is a new graph parameter introduced independently Kam\v{c}ev, {\L}uczak, and Sudakov (2017) and Wilson and Wood (2017). In this note, we show that there are planar graphs of pathwidth 3 with arbitrarily large anagram-free chromatic number.
arxiv
On the Geometric Ramsey Number of Outerplanar Graphs
, 2013 We prove polynomial upper bounds of geometric Ramsey numbers of pathwidth-2 outerplanar triangulations in both convex and general cases. We also prove that the geometric Ramsey numbers of the ladder graph on $2n$ vertices are bounded by $O(n^{3})$ and $O(
Cibulka, Josef +4 more
core +1 more source
Strong-mixed searching and pathwidth [PDF]
Journal of Combinatorial Optimization, 2006 In this paper, we propose a new search model, called strong-mixed search, which is a generalization of the mixed search. We show that the strong-mixed search number of a graph equals the pathwidth of the graph. We also describe relationships between the strong-mixed search number and other search numbers.
openaire +2 more sources
LTL Fragments are Hard for Standard Parameterisations
, 2015 We classify the complexity of the LTL satisfiability and model checking problems for several standard parameterisations. The investigated parameters are temporal depth, number of propositional variables and formula treewidth, resp., pathwidth.
Lück, Martin, Meier, Arne
core +1 more source
Forbidden Directed Minors and Kelly-width [PDF]
, 2014 Partial 1-trees are undirected graphs of treewidth at most one. Similarly, partial 1-DAGs are directed graphs of KellyWidth at most two. It is well-known that an undirected graph is a partial 1-tree if and only if it has no K_3 minor.
Kintali, Shiva, Zhang, Qiuyi
core
Computing cutwidth and pathwidth of semi-complete digraphs via degree orderings [PDF]
arXiv, 2012 The notions of cutwidth and pathwidth of digraphs play a central role in the containment theory for tournaments, or more generally semi-complete digraphs, developed in a recent series of papers by Chudnovsky, Fradkin, Kim, Scott, and Seymour [2, 3, 4, 8, 9, 11]. In this work we introduce a new approach to computing these width measures on semi-complete
arxiv