The minimum vulnerability problem on specific graph classes

DOI10.1007/S10878-015-9950-2MaRDI QIDQ346526zbMATH OpenOpenAlexFDO

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

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 algorithmchordal graphfixed parameter tractabilitybounded treewidth graphminimum vulnerability problem

Mathematics Subject Classification ID

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

Recommendations

• The minimum vulnerability problem on graphs
• The minimum vulnerability problem
• The minimum vulnerability problem
• scientific article; zbMATH DE number 1339493
• scientific article; zbMATH DE number 4053662
• Measuring the vulnerability for classes of intersection graphs
• Vulnerability of subclasses of chordal graphs
• On critical node problems with vulnerable vertices
• Vulnerability of some splitting graphs
• On computing the vulnerability of some graphs as average

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1487883 (Why is no real title available?)
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
• A polynomial-time algorithm for finding total colorings of partial \(k\)-trees
• Beyond the flow decomposition barrier
• Efficient graph representations
• Finding paths with minimum shared edges
• Graph Classes: A Survey
• On network design problems: fixed cost flows and the covering steiner problem
• The edge-disjoint paths problem is NP-complete for series-parallel graphs
• The intersection graphs of subtrees in trees are exactly the chordal graphs
• The minimum vulnerability problem
• The minimum vulnerability problem on graphs

Cited in

(6)

• The parameterized complexity of the minimum shared edges problem
• The minimum vulnerability problem on graphs
• The complexity of routing with collision avoidance
• The minimum vulnerability problem
• The minimum vulnerability problem
• Finding paths with minimum shared edges

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

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