Exact and Approximate Algorithms for Computing a Second Hamiltonian Cycle

DOI10.4230/LIPIcs.MFCS.2020.2OpenAlexW3046947725MaRDI QIDQ5089159

Sergio Cabello

Publication date: 18 July 2022

Full work available at URL: http://dro.dur.ac.uk/31476/

zbMATH Keywords

geometric graphsmaximum matchingfixed-parameter tractabilitybarrier resiliencestochastic computational geometry

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Closest pair and the post office problem for stochastic points
• Range searching with efficient hierarchical cuttings
• On the complexity of barrier resilience for fat regions and bounded ply
• Hardness of minimum barrier shrinkage and minimum installation path
• Maximum matchings in planar graphs via Gaussian elimination
• The Complexity of Counting in Sparse, Regular, and Planar Graphs
• Minimum Cell Connection in Line Segment Arrangements
• An optimal algorithm for intersecting line segments in the plane
• Computing the Expected Value and Variance of Geometric Measures
• Stochastic minimum spanning trees in euclidean spaces
• Geometry helps in bottleneck matching and related problems
• Minimum shared‐power edge cut