Pathwidth is NP-Hard for Weighted Trees

DOI10.1007/978-3-642-02270-8_20MaRDI QIDQ5321709zbMATH OpenOpenAlexFDO

Authors Rodica Mihai, Ioan Todinca

Publication date 14 July 2009

Published in Frontiers in Algorithmics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/978-3-642-02270-8_20

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• On the pathwidth of chordal graphs
• On approximation intractability of the path-distance-width problem
• Faster computation of path-width
• scientific article; zbMATH DE number 4173000
• Clique-width minimization is NP-hard

Cites work

• Characterizing Minimal Interval Completions
• Computing the Minimum Fill-In is NP-Complete
• Computing the vertex separation of unicyclic graphs
• Connected graph searching in chordal graphs
• Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time
• Edge and node searching problems on trees
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• Graph Classes: A Survey
• Graph minors. I. Excluding a forest
• scientific article; zbMATH DE number 3650583 (Why is no real title available?)
• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3590298 (Why is no real title available?)
• scientific article; zbMATH DE number 1990726 (Why is no real title available?)
• Min Cut is NP-complete for edge weighted trees
• Monotonicity in graph searching
• Node-searching problem on block graphs
• On the pathwidth of chordal graphs
• On the Treewidth and Pathwidth of Biconvex Bipartite Graphs
• Pathwidth is NP-Hard for Weighted Trees
• Pathwidth of Circular-Arc Graphs
• Recontamination does not help to search a graph
• Searching and pebbling
• The complexity of searching a graph
• The vertex separation and search number of a graph
• The vertex separation number of a graph equals its path-width
• Treewidth and Pathwidth of Permutation Graphs
• TREEWIDTH OF CIRCLE GRAPHS
• Treewidth of Circular-Arc Graphs

Cited in

(11)

• On the pathwidth of chordal graphs
• Approximate search strategies for weighted trees
• Distributed graph searching with a sense of direction
• A distributed algorithm for computing the node search number in trees
• Clique-width minimization is NP-hard
• Thread graphs, linear rank-width and their algorithmic applications
• Decision Diagram Decomposition for Quadratically Constrained Binary Optimization
• Pathwidth is NP-Hard for Weighted Trees
• On approximation intractability of the path-distance-width problem
• Connected graph searching
• Connected searching of weighted trees

This page was built for publication: Pathwidth is NP-Hard for Weighted Trees

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