Two feedback problems for graphs with bounded tree-width

DOI10.1007/S11766-004-0048-3zbMath1059.05100OpenAlexW2061048290MaRDI QIDQ1764384

Shaoqiang Zhang, Moo Young Sohn, Guo Jun Li

Publication date: 24 February 2005

Published in: Applied Mathematics. Series B (English Edition) (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s11766-004-0048-3

zbMATH Keywords

dynamic programmingtree-widthtree-decompositionfeedback vertex set problemvertex feedback edge set problem

Mathematics Subject Classification ID

Dynamic programming (90C39) Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• Unnamed Item
• Unnamed Item
• Graph minors. I. Excluding a forest
• Linear time algorithms for NP-hard problems restricted to partial k- trees
• A primal-dual interpretation of two 2-approximation algorithms for the feedback vertex set problem in undirected graphs
• Polynomial algorithms for graph isomorphism and chromatic index on partial k-trees
• Easy problems for tree-decomposable graphs
• Complexity of Finding Embeddings in a k-Tree
• On Local Search and Placement of Meters in Networks
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Two feedback problems for graphs with bounded tree-width