Results 111 to 120 of about 11,104 (228)

Parameterized Edge Hamiltonicity

, 2014
We study the parameterized complexity of the classical Edge Hamiltonian Path problem and give several fixed-parameter tractability results. First, we settle an open question of Demaine et al.
AA Bertossi, B Courcelle, B Courcelle, B Courcelle, DG Corneil, ED Demaine, F Gurski, F Gurski, F Harary, FV Fomin, G Chartrand, H-J Lai, HL Bodlaender, I Razgon, J Flum, L Clark, P Dey, P Hliněnỳ, PA Catlin, R Niedermeier, RA Brualdi, RG Downey, S-I Oum, T-H Lai, TH Cormen, W Espelage, Z Ryjácek, Z-H Chen   +27 more
core   +1 more source

Induced subgraphs and tree decompositions V. one neighbor in a hole

Journal of Graph Theory, Volume 105, Issue 4, Page 542-561, April 2024.
Abstract What are the unavoidable induced subgraphs of graphs with large treewidth? It is well‐known that the answer must include a complete graph, a complete bipartite graph, all subdivisions of a wall and line graphs of all subdivisions of a wall (we refer to these graphs as the “basic treewidth obstructions”).
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl, Kristina Vušković   +5 more
wiley   +1 more source

Visualizing Treewidth

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 tree decomposition or path decomposition as a tree of bags, with induced subgraphs shown in each bag,
Chiu, Alvin, Depian, Thomas, Eppstein, David, Goodrich, Michael T., Nöllenburg, Martin   +4 more
openaire   +4 more sources

The tractability frontier of well-designed SPARQL queries

, 2018
We study the complexity of query evaluation of SPARQL queries. We focus on the fundamental fragment of well-designed SPARQL restricted to the AND, OPTIONAL and UNION operators.
Abiteboul S., Flum J., Kaminski M., Kolaitis P., Kostylev E., Kroll M., Pichler S. S. R.   +6 more
core   +1 more source

The product structure of squaregraphs

Journal of Graph Theory, Volume 105, Issue 2, Page 179-191, February 2024.
Abstract A squaregraph is a plane graph in which each internal face is a 4‐cycle and each internal vertex has degree at least 4. This paper proves that every squaregraph is isomorphic to a subgraph of the semistrong product of an outerplanar graph and a path.
Robert Hickingbotham, Paul Jungeblut, Laura Merker, David R. Wood   +3 more
wiley   +1 more source

Product structure of graph classes with bounded treewidth [PDF]

, 2022
Rutger Campbell, Katie Clinch, Marc Distel, J. Pascal Gollin, Kevin Hendrey, Robert Hickingbotham, Tony Huynh, Freddie Illingworth, Youri Tamitegama, Jane Tan, David R. Wood   +10 more
openalex   +1 more source

Semantic Tree-Width and Path-Width of Conjunctive Regular Path Queries [PDF]

Logical Methods in Computer Science
We show that the problem of whether a query is equivalent to a query of tree-width $k$ is decidable, for the class of Unions of Conjunctive Regular Path Queries with two-way navigation (UC2RPQs).
Diego Figueira, Rémi Morvan
doaj   +1 more source

Planar Disjoint Paths, Treewidth, and Kernels [PDF]

, 2023
Michał Włodarczyk, Meirav Zehavi
openalex   +1 more source

Hitting minors on bounded treewidth graphs. III. Lower bounds [PDF]

, 2021
Julien Baste, Ignasi Sau, Dimitrios M. Thilikos   +2 more
openalex   +1 more source

Cop-width, flip-width and strong colouring numbers [PDF]

Discrete Mathematics & Theoretical Computer Science
Cop-width and flip-width are new families of graph parameters introduced by Toru\'nczyk (2023) that generalise treewidth, degeneracy, generalised colouring numbers, clique-width and twin-width.
Robert Hickingbotham
doaj   +1 more source