Exact approaches for the orderly colored longest path problem: performance comparison

DOI10.1016/J.COR.2018.08.005MaRDI QIDQ1628069zbMATH OpenOpenAlexWikidataFDO

Authors Francesco Carrabs, Raffaele Cerulli, Giovanni Felici, Gaurav Singh

Publication date 3 December 2018

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.cor.2018.08.005

zbMATH Keywords

integer programminglongest pathedge colored graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Paths and cycles (05C38)

Recommendations

• The orderly colored longest path problem -- a survey of applications and new algorithms
• Exact and approximate algorithms for the longest induced path problem
• An experimental study of ILP formulations for the longest induced path problem
• An exact approach for the vertex coloring problem
• On the maximum disjoint paths problem on edge-colored graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A Dirac type condition for properly coloured paths and cycles
• An Edge-Colored Version of Dirac's Theorem
• Cycles and paths in edge‐colored graphs with given degrees
• DNA physical mapping and alternating Eulerian cycles in colored graphs
• Hamiltonian circuits determining the order of chromosomes
• Odd Minimum Cut-Sets and b-Matchings
• On the complexity of rainbow spanning forest problem
• Optimal pathway reconstruction on 3D NMR maps
• Properly colored paths and cycles
• The orderly colored longest path problem -- a survey of applications and new algorithms
• The rainbow spanning forest problem
• Variable neighborhood search for the heaviest \(k\)-subgraph

Cited in

(8)

• \(H\)-cycles in \(H\)-colored multigraphs
• A two-level metaheuristic for the all colors shortest path problem
• The orderly colored longest path problem -- a survey of applications and new algorithms
• A generalization of properly colored paths and cycles in edge-colored graphs
• A dynamic programming algorithm for solving the k-color shortest path problem
• An exact reduction technique for the k-colour shortest path problem
• New formulations and branch-and-cut procedures for the longest induced path problem
• Proper vertex-pancyclicity of edge-colored complete graphs without joint monochromatic triangles

This page was built for publication: Exact approaches for the orderly colored longest path problem: performance comparison

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