Edge-treewidth: algorithmic and combinatorial properties

DOI10.1016/j.dam.2023.07.023zbMath1526.05131arXiv2112.07524OpenAlexW4385772980MaRDI QIDQ6069149

Loïc Magne, Abhijat Sharma, Christophe Paul, Dimitrios M. Thilikos

Publication date: 13 November 2023

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2112.07524

zbMATH Keywords

treewidthobstructionsgraph parametersedge-treewidthweak topological minors

Mathematics Subject Classification ID

Trees (05C05) Graph minors (05C83) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The structure of graphs not admitting a fixed immersion
• Graph minors. XX: Wagner's conjecture
• Graph minors. III. Planar tree-width
• Derivation of algorithms for cutwidth and related graph layout parameters
• On tree-partition-width
• Graph minors. I. Excluding a forest
• Graph minors. V. Excluding a planar graph
• The vertex separation number of a graph equals its path-width
• S-functions for graphs
• A partial k-arboretum of graphs with bounded treewidth
• Graph searching and a min-max theorem for tree-width
• The vertex separation and search number of a graph
• Quickly excluding a planar graph
• Treewidth for graphs with small chordality
• Fugitive-search games on graphs and related parameters
• On minimum cuts and the linear arrangement problem
• Tree-width, path-width, and cutwidth
• Graph minors. XIII: The disjoint paths problem
• On tree-partitions of graphs
• On structural parameterizations of the edge disjoint paths problem
• On non-serial dynamic programming
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• The power of cut-based parameters for computing edge-disjoint paths
• A $c^k n$ 5-Approximation Algorithm for Treewidth
• Polynomial Bounds for the Grid-Minor Theorem
• On the Cutwidth and the Topological Bandwidth of a Tree
• Complexity of Finding Embeddings in a k-Tree
• On the Computational Complexity of Combinatorial Problems
• Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree
• Constructive linear time algorithms for branchwidth
• Constructive algorithm for path-width of matroids
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Finding Branch-Decompositions of Matroids, Hypergraphs, and More
• Algorithmic Applications of Tree-Cut Width
• A Linear Fixed Parameter Tractable Algorithm for Connected Pathwidth
• Linear Kernels for Edge Deletion Problems to Immersion-Closed Graph Classes
• Parameterized and Exact Computation
• Cutwidth I: A linear time fixed parameter algorithm
• Cutwidth II: Algorithms for partial w-trees of bounded degree
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The edge-disjoint paths problem is NP-complete for series-parallel graphs

This page was built for publication: Edge-treewidth: algorithmic and combinatorial properties