Layered graph traversals and Hamiltonian path problems---an algebraic approach

DOI10.1007/BFB0054287MaRDI QIDQ4213379zbMATH OpenFDO

Authors Thomas Brunn, Bernhard Möller, Martin Russling

Publication date 25 November 1998

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://nbn-resolving.org/urn:nbn:de:bvb:384-opus4-2179

zbMATH Keywords

algebra of pathsHamiltonian pathsKleene algebrasmatchingsshortest path problem

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10)

Recommendations

• Algorithms for the optimal Hamiltonian path in Halin graphs
• The Hamiltonian problem and \(t\)-path traceable graphs
• An approximation algorithm for finding long paths in Hamiltonian graphs
• Some results dealing with the algebraic approach to path problems in graphs
• Competitive Algorithms for Layered Graph Traversal
• scientific article; zbMATH DE number 1445365
• Hamiltonian paths in L-shaped grid graphs
• Traversing Layered Graphs Using the Work Function Algorithm
• Layers and matroids for the traveling salesman's paths
• scientific article; zbMATH DE number 4091550

Cited in

(6)

• Deriving a class of layer-oriented graph algorithms
• Combining relation algebra and data refinement to develop rectangle-based functional programs for reflexive-transitive closures
• On algebra of program correctness and incorrectness
• Simple rectangle-based functional programs for computing reflexive-transitive closures
• scientific article; zbMATH DE number 876677 (Why is no real title available?)
• Traversing Layered Graphs Using the Work Function Algorithm

This page was built for publication: Layered graph traversals and Hamiltonian path problems---an algebraic approach

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