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
Selected Papers of the 31st International Workshop on Combinatorial Algorithms, IWOCA 2020. [PDF]
Algorithmica, 2022 Gąsieniec L, Klasing R, Radzik T.
europepmc +1 more source
Graph and String Parameters: Connections Between Pathwidth, Cutwidth and the Locality Number [PDF]
arXiv, 2019 We investigate the locality number, a recently introduced structural parameter for strings (with applications in pattern matching with variables), and its connection to two important graph-parameters, cutwidth and pathwidth. These connections allow us to show that computing the locality number is NP-hard, but fixed-parameter tractable, if parameterised
arxiv
Induced subgraphs and tree decompositions XVIII. Obstructions to bounded pathwidth [PDF]
arXivThe pathwidth of a graph $G$ is the smallest $w\in \mathbb{N}$ such that $G$ can be constructed from a sequence of graphs, each on at most $w+1$ vertices, by gluing them together in a linear fashion. We provide a full classification of the unavoidable induced subgraphs of graphs with large pathwidth.
arxiv
Protocol for aerosolization challenge of mice with Bordetella pertussis. [PDF]
STAR Protoc, 2023 Bitzer G +3 more
europepmc +1 more source
Approximation Algorithms for Digraph Width Parameters [PDF]
arXiv, 2011 Several problems that are NP-hard on general graphs are efficiently solvable on graphs with bounded treewidth. Efforts have been made to generalize treewidth and the related notion of pathwidth to digraphs. Directed treewidth, DAG-width and Kelly-width are some such notions which generalize treewidth, whereas directed pathwidth generalizes pathwidth ...
arxiv
Sub-exponential Time Parameterized Algorithms for Graph Layout Problems on Digraphs with Bounded Independence Number. [PDF]
Algorithmica, 2023 Misra P, Saurabh S, Sharma R, Zehavi M.
europepmc +1 more source
Using ILP/SAT to Determine Pathwidth, Visibility Representations, and other Grid-Based Graph Drawings [PDF]
, 2013 Thérèse Biedl +5 more
openalex +1 more source
Tree diet: reducing the treewidth to unlock FPT algorithms in RNA bioinformatics. [PDF]
Algorithms Mol Biol, 2022 Marchand B, Ponty Y, Bulteau L.
europepmc +1 more source