On computing the Hamiltonian index of graphs

DOI10.1016/j.tcs.2022.10.047OpenAlexW4308522709MaRDI QIDQ2699968

M. R. Rani, Geevarghese Philip, 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)

Cites Work

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