Parameterized edge Hamiltonicity
From MaRDI portal
Publication:2413968
DOI10.1016/j.dam.2017.04.045zbMath1395.05098arXiv1403.2041OpenAlexW2614881414MaRDI QIDQ2413968
Valia Mitsou, Yushi Uno, Michael Lampis, Kazuhisa Makino
Publication date: 17 September 2018
Published in: Discrete Applied Mathematics, Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1403.2041
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Eulerian and Hamiltonian graphs (05C45)
Related Items
On Computing the Hamiltonian Index of Graphs ⋮ Optimizing concurrency under Scheduling by Edge Reversal ⋮ Structural parameters, tight bounds, and approximation for \((k, r)\)-center ⋮ On computing the Hamiltonian index of graphs ⋮ Kernelization of Graph Hamiltonicity: Proper $H$-Graphs ⋮ Unnamed Item
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- UNO is hard, even for a single player
- Hamiltonian index is NP-complete
- The edge Hamiltonian path problem is NP-complete
- The edge Hamiltonian path problem is NP-complete for bipartite graphs
- Eulerian subgraphs containing given vertices and hamiltonian line graphs
- Linear time solvable optimization problems on graphs of bounded clique-width
- Line graphs of bounded clique-width
- Parametrized complexity theory.
- Approximating clique-width and branch-width
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- A $c^k n$ 5-Approximation Algorithm for Treewidth
- A Dynamic Programming Approach to Sequencing Problems
- On hamiltonian line graphs
- The Spatial Complexity of Oblivious k-Probe Hash Functions
- Hamiltonian line graphs
- Supereulerian graphs: A survey
- Color-coding
- Eulerian subgraphs in 3‐edge‐connected graphs and Hamiltonian line graphs
- On the Relationship Between Clique-Width and Treewidth
- Cliquewidth and Knowledge Compilation
- The Graph Motif Problem Parameterized by the Structure of the Input Graph
- Solving Connectivity Problems Parameterized by Treewidth in Single Exponential Time
- On Eulerian and Hamiltonian Graphs and Line Graphs
- On Hamiltonian Line-Graphs
