The ferry cover problem

DOI10.1007/S00224-008-9107-0MaRDI QIDQ2272191zbMATHOpenAlexFDO

Authors Michael Lampis, Valia Mitsou

Publication date 6 August 2009

Published in Theory of Computing Systems (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00224-008-9107-0

zbMATH Keywords

approximation algorithmsgraph algorithmsvertex covertransportation problemsWolf-Goat-Cabbage puzzle

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Traffic problems in operations research (90B20)

Recommendations

• The Ferry Cover Problem
• The ferry cover problem on regular graphs and small-degree graphs
• Generalized river crossing problems
• Algorithms and complexity of generalized river crossing problems
• The Alcuin Number of a Graph and Its Connections to the Vertex Cover Number

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 1256636 (Why is no real title available?)
• scientific article; zbMATH DE number 1839431 (Why is no real title available?)
• scientific article; zbMATH DE number 1440124 (Why is no real title available?)
• Approximate max-flow min-(multi)cut theorems and their applications
• Node-and edge-deletion NP-complete problems
• On the complexity of H-coloring
• Optimization, approximation, and complexity classes
• Primal-dual approximation algorithms for feedback problems in planar graphs

Cited in

(4)

• Generalized river crossing problems
• The ferry cover problem on regular graphs and small-degree graphs
• Algorithms and complexity of generalized river crossing problems
• The Ferry Cover Problem

This page was built for publication: The ferry cover problem

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