Pathwidth is NP-Hard for Weighted Trees

DOI10.1007/978-3-642-02270-8_20zbMath1248.68385OpenAlexW1883847458MaRDI QIDQ5321709

Ioan Todinca, Rodica Mihai

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 theory (including graph drawing) in computer science (68R10) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (9)

Pathwidth is NP-Hard for Weighted Trees ⋮ Approximate search strategies for weighted trees ⋮ A distributed algorithm for computing the node search number in trees ⋮ Thread Graphs, Linear Rank-Width and Their Algorithmic Applications ⋮ Connected graph searching ⋮ Connected searching of weighted trees ⋮ Searching by heterogeneous agents ⋮ Decision Diagram Decomposition for Quadratically Constrained Binary Optimization ⋮ Distributed graph searching with a sense of direction

Cites Work

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

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