iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://doi.org/10.1007/s10479-007-0231-z
Local search algorithms for finding the Hamiltonian completion number of line graphs | Annals of Operations Research Skip to main content
Springer Nature Link
Log in

Local search algorithms for finding the Hamiltonian completion number of line graphs

  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

Given a graph G=(V,E), the Hamiltonian completion number of G, HCN(G), is the minimum number of edges to be added to G to make it Hamiltonian. This problem is known to be \(\mathcal{NP}\) -hard even when G is a line graph. In this paper, local search algorithms for finding HCN(G) when G is a line graph are proposed. The adopted approach is mainly based on finding a set of edge-disjoint trails that dominates all the edges of the root graph of G. Extensive computational experiments conducted on a wide set of instances allow to point out the behavior of the proposed algorithms with respect to both the quality of the solutions and the computation time.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  • Agnetis, A., Detti, P., Meloni, C., & Pacciarelli, D. (2001a). Set-up coordination between two stages of a supply chain. Annals of Operations Research, 107, 15–32.

    Article  Google Scholar 

  • Agnetis, A., Detti, P., Meloni, C., & Pacciarelli, D. (2001b). A linear algorithm for the Hamiltonian completion number of the line graph of a tree. Information Processing Letters, 79, 17–24.

    Article  Google Scholar 

  • Agnetis, A., Detti, P., & Meloni, C. (2003). Process selection and sequencing in a two-agents production system. 4OR, 1(2), 103–119.

    Article  Google Scholar 

  • Aigner, M., & Andreae, T. (1989). The total interval number of a graph. Journal of Combinatorial Theory Series B, 46, 7–21.

    Article  Google Scholar 

  • Applegate, D., Bixby, R., Chvàtal, V., & Cook, W. (2003). Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems. Mathematical Programming, 97, 91–153.

    Google Scholar 

  • Balas, E., & Vazacopoulos, A. (1998). Guided local search with shifting bottleneck for job shop scheduling. Management Science, 44(2), 262–275.

    Article  Google Scholar 

  • Bertossi, A. A. (1981). The edge Hamiltonian problem is NP-hard. Information Processing Letters, 13, 157–159.

    Article  Google Scholar 

  • Bonuccelli, M. A., & Bovet, D. P. (1979). Minimum node disjoint path covering for circular-arc graphs. Information Processing Letters, 8(4), 159–161.

    Article  Google Scholar 

  • den Besten, M., Stützle, T., & Dorigo, M. (2001). Design of iterated local search algorithms: an example application to the single machine total weighted tardiness problem. In Lecture notes in computer science (Vol. 2037, pp. 441–451).

  • Detti, P., & Meloni, C. (2001). Part type selection and batch sequencing in a two-stage manufacturing system. In Proceedings of 16th international conference on production research, Praha.

  • Detti, P., & Meloni, C. (2004). A linear algorithm for the Hamiltonian completion number of the line graph of a cactus. Discrete Applied Mathematics, 136, 197–215.

    Article  Google Scholar 

  • Detti, P., Meloni, C., & Pranzo, M. (2004). Simple bounds for the minimum cardinality dominating trail set problem (Technical report RT-DIA-87-2004). Dipartimento di Informatica e Automazione, Università Roma Tre, Roma, Italy.

  • Gamarnik, D., & Sviridenko, M. (2005). Hamiltonian completions of sparse random graphs. Discrete Applied Mathematics, 152, 139–158.

    Article  Google Scholar 

  • Hansen, P., & Mladenovic, N. (2001). Variable neighborhood search: principles and applications. European Journal of Operational Research, 130, 449–467.

    Article  Google Scholar 

  • Harary, F., & Nash-Williams, C. S. J. A. (1965). On Eulerian and Hamiltonian graphs and line-graphs. Canadian Mathematics Bulletin, 8, 701–709.

    Google Scholar 

  • Hoos, H. H., & Stützle, T. (2004). Stochastic local search—foundations & applications. San Francisco: Morgan Kaufmann.

    Google Scholar 

  • Johnson, D. S., & McGeoch, L. A. (1997). The travelling salesman problem: a case study in local optimization. In Local search in combinatorial optimization (pp. 215–310). New York: Wiley.

    Google Scholar 

  • Kratzke, T. M., & West, D. B. (1993). The total interval number of a graph, I: fundamental classes. Discrete Mathematics, 118, 145–156.

    Article  Google Scholar 

  • Kundu, S. (1976). A linear algorithm for the Hamiltonian completion number of a tree. Information Processing Letters, 5, 55–57.

    Article  Google Scholar 

  • Lai, T. H., & Wei, S. S. (1995). Algorithms for page retrieval and Hamiltonian paths on forward-convex line graphs. Journal of Algorithms, 18, 358–375.

    Article  Google Scholar 

  • Lehot, P. G. H. (1974). An optimal algorithm to detect a line graph and output its root graph. Journal of the ACM, 21, 569–575.

    Article  Google Scholar 

  • Lin, R., Olariu, S., & Pruesse, G. (1995). An optimal path cover algorithm for cographs. Computers and Mathematics with Applications, 30(8), 75–83.

    Article  Google Scholar 

  • Lourenço, H. R. D., Martin, O., & Stützle, T., (2002). Iterated local search. In F. Glover & G. Kochenberger (Eds.), Handbook of metaheuristics (pp. 321–353). Dordrecht: Kluwer Academic.

    Google Scholar 

  • Nikolopoulos, S. D. (2004). Parallel algorithms for Hamiltonian problems on quasi-threshold graphs. Journal of Parallel and Distributed Computing, 64, 48–67.

    Article  Google Scholar 

  • Rao Arikati, S., & Pandu Rangan, C. (1990). Linear algorithm for optimal path cover problem on interval graphs. Information Processing Letters, 35, 149–153.

    Article  Google Scholar 

  • Raychaudhuri, A. (1995). The total interval number of a tree and the Hamiltonian completion number of its line graph. Information Processing Letters, 56, 299–306.

    Article  Google Scholar 

  • Roussopoulos, N. D. (1973). A max {m,n} algorithm for determining the graph H from its line graph G. Information Processing Letters, 2, 108–112.

    Article  Google Scholar 

  • Skupień, Z. (1976). Hamiltonian shortage, path partitions of vertices, and matchings in a graph. Colloquium Mathematicum, 36(2), 305–318.

    Google Scholar 

  • Smyth, K., Hoos, H. H., & Stützle, T. (2003). Iterated robust tabu search for MAX-SAT. In Lecture notes in computer science (Vol. 2671, pp. 129–144).

  • Srikant, R., Sundaram, R., Singh, K. S., & Pandu Rangan, C. (1993). Optimal path cover problem on block graphs and bipartite permutation graphs. Theoretical Computer Science, 115, 351–357.

    Article  Google Scholar 

  • Stützle, T. (1998). Applying iterated local search to the permutation flow shop problem (Technical report AIDA-98-04). FG Intellektik, TU Darmstadt.

  • Veldman, H. J. (1988). A result on Hamiltonian line graphs involving restrictions on induced subgraphs. Journal of Graph Theory, 12(3), 413–420.

    Article  Google Scholar 

  • Voß, S., Martello, S., Osman, I.H., & Roucairol, C. (Eds.). (1999). Meta-heuristics: advances and trends in local search paradigms for optimization. Dordrecht: Kluwer Academic.

    Google Scholar 

  • Wu, Q. S., Lu, C. L., & Lee, R. C. T. (2000). An approximate algorithm for the weighted Hamiltonian path completion problem on a tree. In Lecture notes in computer science (Vol. 1969, pp. 156–167).

Download references

Author information

Authors and Affiliations

  1. Dipartimento di Ingegneria dell’Informazione, Università di Siena, Siena, Italy

    Paolo Detti & Marco Pranzo

  2. Dipartimento di Elettrotecnica ed Elettronica, Politecnico di Bari, Bari, Italy

    Carlo Meloni

Authors
  1. Paolo Detti
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Carlo Meloni
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Marco Pranzo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Paolo Detti.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Detti, P., Meloni, C. & Pranzo, M. Local search algorithms for finding the Hamiltonian completion number of line graphs. Ann Oper Res 156, 5–24 (2007). https://doi.org/10.1007/s10479-007-0231-z

Download citation

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10479-007-0231-z

Keywords

Search

Navigation