Results 91 to 100 of about 1,033 (146)

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

New algorithms for pathwidth computation

, 2004
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.
Li, Ming
core  

Minimal Forbidden Directed Minors and Directed Pathwidth

, 2014
Directed pathwidth is a natural generalization of pathwidth to digraphs. It is well-known that undirected graphs of pathwidth at most one are characterized by two forbidden minors [BFKL87].
Zhang, Qiuyi Richard
core  

Visualizing Treewidth

Journal of Graph Algorithms and Applications
A witness drawing of a graph is a visualization that clearly shows a given property of a graph. We study and implement various drawing paradigms for witness drawings to clearly show that graphs have bounded pathwidth or treewidth. Our approach draws the
Alvin Chiu, Thomas Depian, David Eppstein, Michel T. Goodrich, Martin Nöllenburg   +4 more
doaj   +1 more source

Structural Parameterizations of $k$-Planarity

Journal of Graph Algorithms and Applications
The concept of $k$-planarity is extensively studied in the context of Beyond Planarity. A graph is $k$-planar if it admits a drawing in the plane in which each edge is crossed at most $k$ times.
Tatsuya Gima, Yasuaki Kobayashi, Yuto Okada   +2 more
doaj   +1 more source

Protocol for aerosolization challenge of mice with Bordetella pertussis. [PDF]

STAR Protoc, 2023
Bitzer G, Weaver K, Barbier M, Damron FH.   +3 more
europepmc   +1 more source

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

The Primal Pathwidth SETH

To appear in SODA ...
openaire   +4 more sources

Pathwidth is NP-Hard for Weighted Trees

, 2009
International audienceThe pathwidth of a graph G is the minimum clique number of H minus one, over all interval supergraphs H of G. We prove in this paper that the pathwidth problem is NP-hard for particular subclasses of chordal graphs, and we deduce ...
Ioan Todinca, Rodica Mihai, Todinca, Ioan, Mihai, Rodica   +3 more
core   +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