Efficient algorithms for some path partitioning problems

DOI10.1016/0166-218X(94)00146-5MaRDI QIDQ1900138zbMATH OpenFDO

Authors Peter Brucker

Publication date 22 November 1995

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

clusteringimage processingone-machine batching

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Deterministic scheduling theory in operations research (90B35) Combinatorial optimization (90C27) Dynamic programming (90C39)

Recommendations

• A New Polynomially Bounded Shortest Path Algorithm
• An Appraisal of Some Shortest-Path Algorithms
• Improved algorithms for path partition and related problems
• Efficient points on a network
• On the minimax path in a network

Cites work

• scientific article; zbMATH DE number 432797 (Why is no real title available?)
• Batch sizing and job sequencing on a single machine
• Most uniform path partitioning and its use in image processing
• Sequence comparison with mixed convex and concave costs
• The complexity of one-machine batching problems

Cited in

(9)

• scientific article; zbMATH DE number 4031432 (Why is no real title available?)
• Path partitions and forward-only trellis algorithms
• Minimum \(L_k\) path partitioning-an illustration of the Monge property
• A note on the partitioning shortest path algorithm
• A fast randomized algorithm for partitioning a graph into paths of fixed length
• Most uniform path partitioning and its use in image processing
• Path optimization for graph partitioning problems
• Improved algorithms for path partition and related problems
• scientific article; zbMATH DE number 910878 (Why is no real title available?)

This page was built for publication: Efficient algorithms for some path partitioning problems

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