On Strong Tree-Breadth

DOI10.1007/978-3-319-48749-6_5zbMath1427.68248OpenAlexW2540696427MaRDI QIDQ2958304

Arne Leitert, Feodor F. Dragan

Publication date: 1 February 2017

Published in: Combinatorial Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-48749-6_5

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (3)

Equivalence between pathbreadth and strong pathbreadth ⋮ A short note on the complexity of computing strong pathbreadth ⋮ On the complexity of computing treebreadth

Cites Work

• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Polynomial-time algorithms for weighted efficient domination problems in AT-free graphs and dually chordal graphs
• Line-distortion, bandwidth and path-length of a graph
• Graph minors. III. Planar tree-width
• On compact and efficient routing in certain graph classes
• Graph minors. I. Excluding a forest
• Distance-hereditary graphs
• S-functions for graphs
• The algorithmic use of hypertree structure and maximum neighbourhood orderings
• Tree-decompositions with bags of small diameter
• On the Complexity of Computing Treebreadth
• Simple Linear-Time Algorithms to Test Chordality of Graphs, Test Acyclicity of Hypergraphs, and Selectively Reduce Acyclic Hypergraphs
• Dually Chordal Graphs
• Efficient Dominating and Edge Dominating Sets for Graphs and Hypergraphs
• The complexity of satisfiability problems
• Navigating in a Graph by Aid of Its Spanning Tree Metric
• A simple paradigm for graph recognition: Application to cographs and distance hereditary graphs

This page was built for publication: On Strong Tree-Breadth