A lower bound on the Hamiltonian path completion number of a line graph

DOI10.1016/J.AMC.2013.06.020zbMATH Open1329.05251OpenAlexW2013110476MaRDI QIDQ902504FDOQ902504

Authors: Paolo Detti, C. Meloni, Marco Pranzo 

Publication date: 18 January 2016

Published in: Applied Mathematics and Computation (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.amc.2013.06.020

Recommendations

• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• scientific article; zbMATH DE number 1094037
• scientific article; zbMATH DE number 1439412
• Local search algorithms for finding the Hamiltonian completion number of line graphs
• scientific article; zbMATH DE number 1185618
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• A lower bound for the shortest Hamiltonean path in directed graphs
• A result on Hamiltonian line graphs involving restrictions on induced subgraphs
• scientific article; zbMATH DE number 3946175
• On hamiltonian line graphs of hypergraphs

zbMATH Keywords

lower boundline graphsdominating trailHamiltonian path completion number

Mathematics Subject Classification ID

Eulerian and Hamiltonian graphs (05C45) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Depth-First Search and Linear Graph Algorithms
• Title not available (Why is that?)
• Halin graphs and the travelling salesman problem
• On Eulerian and Hamiltonian Graphs and Line Graphs
• Set-up coordination between two stages of a supply chain
• Implementing the Dantzig-Fulkerson-Johnson algorithm for large traveling salesman problems
• The edge Hamiltonian path problem is NP-complete
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• The total interval number of a tree and the Hamiltonian completion number of its line graph
• A result on Hamiltonian line graphs involving restrictions on induced subgraphs
• Algorithms for Page Retrieval and Hamiltonian Paths on Forward-Convex Line Graphs
• Title not available (Why is that?)
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• Process selection and sequencing in a two-agents production system
• Parallel algorithms for Hamiltonian problems on quasi-threshold graphs
• Local search algorithms for finding the Hamiltonian completion number of line graphs
• A bi-objective coordination setup problem in a two-stage production system
• Limit distribution for the existence of Hamiltonian cycles in a random graph. (Reprint)
• The approximability of the weighted Hamiltonian path completion problem on a tree
• Hamiltonian completions of sparse random graphs

Cited In (6)

• A linear algorithm for the Hamiltonian completion number of the line graph of a tree
• A lower bound for the optimal crossing-free Hamiltonian cycle problem
• Evolutionary operators for the Hamiltonian completion problem
• A linear algorithm for the Hamiltonian completion number of the line graph of a cactus.
• Local search algorithms for finding the Hamiltonian completion number of line graphs
• A bi-objective coordination setup problem in a two-stage production system

This page was built for publication: A lower bound on the Hamiltonian path completion number of a line graph

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