Cover Image

The Behavior of Tree-Width and Path-Width under Graph Operations and Graph Transformations

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Gurski, Frank, Weishaupt, Robin
Format:	Preprint
Published:	2024
Subjects:	Data Structures and Algorithms 05C76, 68R10
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Optimal Adjacency Labels for Subgraphs of Cartesian Products
by: Esperet, Louis, et al.
Published: (2022)

Degree Realization by Bipartite Cactus Graphs
by: Bar-Noy, Amotz, et al.
Published: (2025)

The Algorithmic Phase Transition of Random Graph Alignment Problem
by: Du, Hang, et al.
Published: (2023)

On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction
by: Onofri, Elia
Published: (2024)

Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
by: Levet, Michael, et al.
Published: (2023)

Reconfiguration of Independent Transversals
by: Buys, Pjotr, et al.
Published: (2024)

Cops and Robbers on Multi-Layer Graphs
by: Enright, Jessica, et al.
Published: (2023)

Optimal Online Bipartite Matching in Degree-2 Graphs
by: Bhangale, Amey, et al.
Published: (2025)

The Upper Clique Transversal Problem
by: Milanič, Martin, et al.
Published: (2023)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
by: Munaro, Andrea, et al.
Published: (2022)

Orientability of Undirected Phylogenetic Networks to a Desired Class: Practical Algorithms and Application to Tree-Child Orientation
by: Urata, Tsuyoshi, et al.
Published: (2024)

Solving the Graph Burning Problem for Large Graphs
by: Pereira, Felipe de Carvalho, et al.
Published: (2024)

Exact Algorithms for MaxCut on Split Graphs
by: Lalovic, Marko
Published: (2024)

Untangling Graphs on Surfaces
by: de Verdière, Éric Colin, et al.
Published: (2023)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
by: Oum, Sang-il, et al.
Published: (2026)

State Canonization and Early Pruning in Width-Based Automated Theorem Proving
by: Oliveira, Mateus de Oliveira, et al.
Published: (2026)

Decline and Fall of the ICALP 2008 Modular Decomposition algorithm
by: Atherton, William, et al.
Published: (2024)

Closeness and Residual Closeness of Harary Graphs
by: Golpek, Hande Tuncel, et al.
Published: (2023)

Fully Dynamic Breadth First Search and Spanning Trees in Directed Graphs
by: Morse, Gregory, et al.
Published: (2026)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
by: Hommelsheim, Felix
Published: (2025)

Branch-width of represented matroids in matrix multiplication time
by: Choi, Mujin, et al.
Published: (2026)

Identification to Subclasses of Chordal Graphs
by: Golovach, Petr A., et al.
Published: (2026)

Embedding Graphs of Simple Treewidth into Sparse Products
by: Hendrey, Kevin, et al.
Published: (2025)

m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

The Minimum Eternal Vertex Cover Problem on a Subclass of Series-Parallel Graphs
by: Calamoneri, Tiziana, et al.
Published: (2025)

Polynomial-Time Solutions for Longest Common Subsequence Related Problems Between a Sequence and a Pangenome Graph
by: Li, Xingfu, et al.
Published: (2026)

On the Complexity of Distance-$d$ Independent Set Reconfiguration
by: Hoang, Duc A.
Published: (2022)

Optimized Degree Realization: Minimum Dominating Set & Maximum Matching
by: Bar-Noy, Amotz, et al.
Published: (2025)

Obstructions to Erdős-Pósa Dualities for Minors
by: Paul, Christophe, et al.
Published: (2024)

Killing a Vortex
by: Thilikos, Dimitrios M., et al.
Published: (2022)

Binary Jumbled Indexing: Suffix tree histogram
by: Cunha, Luís, et al.
Published: (2024)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
by: Liao, I-Cheng, et al.
Published: (2023)

Optimal Bounds for the k-Disjoint Paths Problem
by: Cavallaro, Dario, et al.
Published: (2026)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
by: Morelle, Laure, et al.
Published: (2025)

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
by: Chiu, Yung-Chung, et al.
Published: (2021)

Bounds on the Twin-Width of Product Graphs
by: Pettersson, William, et al.
Published: (2022)

Colorful Minors
by: Protopapas, Evangelos, et al.
Published: (2025)

A $4/3$ Approximation for $2$-Vertex-Connectivity
by: Bosch-Calvo, Miguel, et al.
Published: (2023)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
by: Lima, Paloma T., et al.
Published: (2024)

Tight bounds on adjacency labels for monotone graph classes
by: Bonnet, Édouard, et al.
Published: (2023)