On computing the Hamiltonian index of graphs

DOI10.1016/J.TCS.2022.10.047MaRDI QIDQ2699968zbMATH OpenOpenAlexFDO

Authors Geevarghese Philip, M. R. Rani, R. Subashini

Publication date 20 April 2023

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2022.10.047

zbMATH Keywords

treewidthfixed-parameter tractabilityparameterized complexitysupereulerian graphsHamiltonian indexiterated line graphsspanning Eulerian subgraphseulerian Steiner subgraphs

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Recommendations

• On Computing the Hamiltonian Index of Graphs
• Hamiltonian iterated line graphs
• Hamiltonian index is NP-complete
• On the Hamiltonian index
• scientific article; zbMATH DE number 6500708

Cites work

• scientific article; zbMATH DE number 1161249 (Why is no real title available?)
• scientific article; zbMATH DE number 3438910 (Why is no real title available?)
• (Some of) the many uses of Eulerian graphs in graph theory (plus some applications)
• A note on graphs spanned by Eulerian graphs
• A partial k-arboretum of graphs with bounded treewidth
• A textbook of graph theory
• Approximate tree decompositions of planar graphs in linear time
• Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth
• Efficient computation of representative families with applications in parameterized and exact algorithms
• Eulerian subgraphs and Hamilton-connected line graphs
• Existence of dominating cycles and paths
• Fundamentals of parameterized complexity
• Hamilton cycles and closed trails in iterated line graphs
• Hamiltonian index is NP-complete
• Hamiltonian iterated line graphs
• Multiplying matrices faster than coppersmith-winograd
• On Eulerian and Hamiltonian Graphs and Line Graphs
• On Hamiltonian Line-Graphs
• On Spanning and Dominating Circuits in Graphs
• On finding spanning eulerian subgraphs
• On line graphs and the Hamiltonian index
• On the Hamiltonian index
• On the parameterized complexity of edge-linked paths
• Parameterized algorithms
• Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
• Subexponential parameterized algorithms for degree-constrained subgraph problems on planar graphs
• Supereulerian graphs: A survey
• The Hamiltonian index of a graph and its branch-bonds
• The Hamiltonian index of graphs
• The Planar Hamiltonian Circuit Problem is NP-Complete
• The edge Hamiltonian path problem is NP-complete
• Treewidth. Computations and approximations

Cited in

(7)

• The Hamiltonian index of a graph and its branch-bonds
• scientific article; zbMATH DE number 6500708 (Why is no real title available?)
• Hamiltonian index is NP-complete
• On Computing the Hamiltonian Index of Graphs
• On testing Hamiltonicity of graphs
• Computing complete graph isomorphisms and Hamiltonian cycles from partial ones
• scientific article; zbMATH DE number 3847432 (Why is no real title available?)

This page was built for publication: On computing the Hamiltonian index of graphs

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