Computing and Sampling Restricted Vertex Degree Subgraphs and Hamiltonian Cycles

Scott Sheffield⋆

Type: Preprint

Publication Date: 2000-01-01

Citations: 5

DOI: https://doi.org/10.48550/arxiv.math/0008231

View Publication

Locations

arXiv (Cornell University) - View
DataCite API - View

Similar Works

Action	Title	Year	Authors
+	Optimal spread for spanning subgraphs of Dirac hypergraphs	2023	Tom Kelly Alp Müyesser Alexey Pokrovskiy
+	A polynomial-time algorithm to determine (almost) Hamiltonicity of dense regular graphs	2020	Viresh Patel Fabian Stroh
+ PDF Chat	A Polynomial-Time Algorithm to Determine (Almost) Hamiltonicity of Dense Regular Graphs	2022	Viresh Patel Fabian Stroh
+	Low Polynomial Exclusion of Planar Graph Patterns	2013	Jean‐Florent Raymond Dimitrios M. Thilikos
+	Low Polynomial Exclusion of Planar Graph Patterns	2013	Jean‐Florent Raymond Dimitrios M. Thilikos
+	Hamilton cycles, minimum degree and bipartite holes	2016	Colin McDiarmid Nikola Yolov
+ PDF Chat	A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs	2022	Dániel Marx Pranabendu Misra Daniel Neuen Prafullkumar Tale
+	Oriented discrepancy of Hamilton cycles	2022	Lior Gishboliner Michael Krivelevich Peleg Michaeli
+ PDF Chat	Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on <i>H</i>-Minor-Free Graphs	2022	Sayan Bandyapadhyay William Lochet Daniel Lokshtanov Saket Saurabh Jie Xue
+ PDF Chat	Excluding a rectangular grid	2025	Clément Rambaud
+	Directed Hamiltonicity and Out-Branchings via Generalized Laplacians	2016	Andreas Björklund Petteri Kaski Ioannis Koutis
+	Counting and packing Hamilton cycles in dense graphs and oriented graphs	2012	Asaf Ferber Michael Krivelevich Benny Sudakov
+	Graph partition method based on finite projective planes	2023	Oleg Kruglov Anna Mastikhina Oleg Senkevich Dmitry Sirotkin Stanislav Moiseev
+ PDF Chat	An explicit construction of graphs of bounded degree that are far from being Hamiltonian	2022	Isolde Adler Noleen Köhler
+	Counting and packing Hamilton cycles in dense graphs and oriented graphs	2012	Asaf Ferber Michael Krivelevich Benny Sudakov
+	Optimal spread for spanning subgraphs of Dirac hypergraphs	2024	Tom Kelly Alp Müyesser Alexey Pokrovskiy
+	Grid Induced Minor Theorem for Graphs of Small Degree	2022	Tuukka Korhonen
+	Grid induced minor theorem for graphs of small degree	2023	Tuukka Korhonen
+ PDF Chat	A Deterministic Polynomial Kernel for Odd Cycle Transversal and Vertex Multiway Cut in Planar Graphs	2021	Bart M. P. Jansen Marcin Pilipczuk Erik Jan van Leeuwen
+ PDF Chat	Kernelization of Graph Hamiltonicity: Proper $H$-Graphs	2021	Steven Chaplick Fedor V. Fomin Petr A. Golovach Dušan Knop Peter Zeman

Works That Cite This (3)

Action	Title	Year	Authors
+	Contributions to graph theory	2005	Muhammad Salman
+	Ribbon Tilings and Multidimensional Height Functions	2001	Scott Sheffield⋆
+ PDF Chat	Ribbon tilings and multidimensional height functions	2002	Scott Sheffield⋆

Works Cited by This (18)

Action	Title	Year	Authors
+	A Basic Course in Algebraic Topology	1991	William S. Massey
+	The statistics of dimers on a lattice	1961	Piet Kasteleyn
+	Which grids are Hamiltonian	1980	Sandra M. Hedetniemi Stephen T. Hedetniemi Peter J. Slater
+	A linear algorithm for perfect matching in hexagonal systems	1993	Pierre Hansen Maolin Zheng
+	On Counting Lattice Points in Polyhedra	1991	Martin Dyer
+	Exact sampling with coupled Markov chains and applications to statistical mechanics	1996	James Propp David Bruce Wilson
+	Hexagonal systems with forcing single edges	1997	Xueliang Li
+ PDF Chat	A random polynomial-time algorithm for approximating the volume of convex bodies	1991	Martin Dyer Alan Frieze Ravi Kannan
+	The Computational Complexity of Counting	1995	Mark Jerrum
+ PDF Chat	An interruptible algorithm for perfect sampling via Markov chains	1998	James Allen Fill