The minimum vulnerability problem on specific graph classes

DOI10.1007/s10878-015-9950-2zbMath1356.90148OpenAlexW2178803989MaRDI QIDQ346526

Bjarni V. Halldórsson, Christian Konrad, Xiao Zhou, Magnús M. Halldórsson, Yusuke Aoki, Takehiro Ito

Publication date: 29 November 2016

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-015-9950-2

zbMATH Keywords

graph algorithmfixed parameter tractabilitychordal graphbounded treewidth graphminimum vulnerability problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Related Items (2)

The complexity of routing with collision avoidance ⋮ The parameterized complexity of the minimum shared edges problem

Cites Work

• Finding paths with minimum shared edges
• Efficient graph representations
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The Minimum Vulnerability Problem on Graphs
• On network design problems: fixed cost flows and the covering steiner problem
• Beyond the flow decomposition barrier
• Graph Classes: A Survey
• The Minimum Vulnerability Problem
• A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• Unnamed Item
• Unnamed Item

This page was built for publication: The minimum vulnerability problem on specific graph classes