A short note on the complexity of computing strong pathbreadth

DOI10.1016/j.ipl.2018.01.005zbMath1427.68237OpenAlexW2791129715MaRDI QIDQ1705708

Guillaume Ducoffe

Publication date: 16 March 2018

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2018.01.005

zbMATH Keywords

computational complexitygraph theoryNP-completenesspath decompositionacyclic clusteringstrong pathbreadth

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 (2)

Equivalence between pathbreadth and strong pathbreadth ⋮ On the complexity of computing treebreadth

Cites Work

• Unnamed Item
• An approximation algorithm for the tree \(t\)-spanner problem on unweighted graphs via generalized chordal graphs
• Graph minors. III. Planar tree-width
• On the complexity of computing treelength
• On compact and efficient routing in certain graph classes
• Tree-decompositions with bags of small diameter
• On the Complexity of Computing Treebreadth
• On Strong Tree-Breadth
• Line-Distortion, Bandwidth and Path-Length of a Graph
• Representation of a finite graph by a set of intervals on the real line
• Treewidth: Characterizations, Applications, and Computations
• Graph Sandwich Problems
• Maximum matching in a convex bipartite graph
• To Approximate Treewidth, Use Treelength!
• On intervalizing \(k\)-colored graphs for DNA physical mapping

This page was built for publication: A short note on the complexity of computing strong pathbreadth