Computing Hamiltonian paths with partial order restrictions
From MaRDI portal
Paths and cycles (05C38) Eulerian and Hamiltonian graphs (05C45) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)
Cites work
- A \(\frac{5}{3}\)-approximation algorithm for the clusterd traveling salesman tour and path problems
- A Cutting Plane Approach to the Sequential Ordering Problem (with Applications to Job Scheduling in Manufacturing)
- A decomposition theorem for partially ordered sets
- A Linear Time Algorithm for the 1-Fixed-Endpoint Path Cover Problem on Interval Graphs
- A linear‐time algorithm for the k‐fixed‐endpoint path cover problem on cographs
- A partial k-arboretum of graphs with bounded treewidth
- A polynomial solution to the \(k\)-fixed-endpoint path cover problem on proper interval graphs
- A polynomial-time algorithm for MCS partial search order on chordal graphs
- A set of independent postulates for cyclic order.
- A Unified View of Graph Searching
- Algorithmic graph theory and perfect graphs
- An efficient parallel strategy for the two-fixed-endpoint Hamiltonian path problem on distance-hereditary graphs
- An inexact algorithm for the sequential ordering problem
- An optimal algorithm for the k-fixed-endpoint path cover on proper interval graphs
- Approximation algorithms for the maximum Hamiltonian path problem with specified endpoint(s)
- Certifying fully dynamic algorithms for recognition and Hamiltonicity of threshold and chain graphs
- Characterizations of outerplanar graphs
- Cyclic ordering is NP-complete
- Cyclically ordered sets
- Easy problems for tree-decomposable graphs
- Exact And Heuristic Procedures For The Traveling Salesman Problem With Precedence Constraints, Based On Dynamic Programming
- Extendability of cyclic orders
- Extended Abstracts EuroComb 2021
- Finding Hamiltonian circuits in interval graphs
- Graph searches and their end vertices
- Hamilton Paths in Grid Graphs
- Hamiltonian Paths and Cycles in Planar Graphs
- scientific article; zbMATH DE number 4027206 (Why is no real title available?)
- scientific article; zbMATH DE number 4072711 (Why is no real title available?)
- scientific article; zbMATH DE number 3639144 (Why is no real title available?)
- scientific article; zbMATH DE number 6737879 (Why is no real title available?)
- Influence of the tie-break rule on the end-vertex problem
- LDFS-based certifying algorithm for the minimum path cover problem on cocomparability graphs
- Linear algorithms to recognize outerplanar and maximal outerplanar graphs
- Linear time LexDFS on cocomparability graphs
- Linearizing partial search orders
- Lower bounds based on the exponential time hypothesis
- Minimizing setups in ordered sets of fixed width
- Obtaining a triangular matrix by independent row-column permutations
- On end-vertices of lexicographic breadth first searches
- On the end-vertex problem of graph searches
- On the parameterized complexity of multiple-interval graph problems
- On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
- Parameterized algorithms
- Postman tour on a graph with precedence relation on arcs
- Recognition algorithms for orders of small width and graphs of small Dilworth number
- Reducing Path TSP to TSP
- Sets of completely independent postulates for cyclic order.
- The 1-fixed-endpoint path cover problem is Polynomial on interval graphs
- The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
- The path-partition problem in bipartite distance-hereditary graphs
- The traveling salesman problem with few inner points
- The travelling salesman problem with precedence constraints.
- Topological orderings of weighted directed acyclic graphs
- Which problems have strongly exponential complexity?
- Worst-case analysis of a new heuristic for the travelling salesman problem
This page was built for publication: Computing Hamiltonian paths with partial order restrictions
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6994668)
