On strong tree-breadth

DOI10.1007/978-3-319-48749-6_5MaRDI QIDQ2958304zbMATH OpenOpenAlexFDO

Authors 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)

Recommendations

• On the complexity of computing treebreadth
• A short note on the complexity of computing strong pathbreadth
• On the complexity of computing treebreadth
• Equivalence between pathbreadth and strong pathbreadth
• Minimum size tree-decompositions

Cites work

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

Cited in

(6)

• Strong WQO Tree Theorems
• On the complexity of computing treebreadth
• On the complexity of computing treebreadth
• Strong tree-cographs are Birkhoff graphs
• Equivalence between pathbreadth and strong pathbreadth
• A short note on the complexity of computing strong pathbreadth

This page was built for publication: On strong tree-breadth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2958304)