Published in: LIPIcs, Volume 283, 34th International Symposium on Algorithms and Computation (ISAAC 2023)
David Eppstein and Daniel Frishberg. Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs. In 34th International Symposium on Algorithms and Computation (ISAAC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 283, pp. 30:1-30:13, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{eppstein_et_al:LIPIcs.ISAAC.2023.30, author = {Eppstein, David and Frishberg, Daniel}, title = {{Rapid Mixing for the Hardcore Glauber Dynamics and Other Markov Chains in Bounded-Treewidth Graphs}}, booktitle = {34th International Symposium on Algorithms and Computation (ISAAC 2023)}, pages = {30:1--30:13}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-289-1}, ISSN = {1868-8969}, year = {2023}, volume = {283}, editor = {Iwata, Satoru and Kakimura, Naonori}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2023.30}, URN = {urn:nbn:de:0030-drops-193324}, doi = {10.4230/LIPIcs.ISAAC.2023.30}, annote = {Keywords: Glauber dynamics, mixing time, projection-restriction, multicommodity flow} }
Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)
Charilaos Efthymiou, Thomas P. Hayes, Daniel Štefankovič, and Eric Vigoda. Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 33:1-33:16, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{efthymiou_et_al:LIPIcs.APPROX/RANDOM.2023.33, author = {Efthymiou, Charilaos and Hayes, Thomas P. and \v{S}tefankovi\v{c}, Daniel and Vigoda, Eric}, title = {{Optimal Mixing via Tensorization for Random Independent Sets on Arbitrary Trees}}, booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)}, pages = {33:1--33:16}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-296-9}, ISSN = {1868-8969}, year = {2023}, volume = {275}, editor = {Megow, Nicole and Smith, Adam}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.33}, URN = {urn:nbn:de:0030-drops-188589}, doi = {10.4230/LIPIcs.APPROX/RANDOM.2023.33}, annote = {Keywords: MCMC, Mixing Time, Independent Sets, Hard-Core Model, Approximate Counting Algorithms, Sampling Algorithms} }
Published in: LIPIcs, Volume 261, 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)
David Eppstein and Daniel Frishberg. Improved Mixing for the Convex Polygon Triangulation Flip Walk. In 50th International Colloquium on Automata, Languages, and Programming (ICALP 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 261, pp. 56:1-56:17, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2023)
@InProceedings{eppstein_et_al:LIPIcs.ICALP.2023.56, author = {Eppstein, David and Frishberg, Daniel}, title = {{Improved Mixing for the Convex Polygon Triangulation Flip Walk}}, booktitle = {50th International Colloquium on Automata, Languages, and Programming (ICALP 2023)}, pages = {56:1--56:17}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-278-5}, ISSN = {1868-8969}, year = {2023}, volume = {261}, editor = {Etessami, Kousha and Feige, Uriel and Puppis, Gabriele}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2023.56}, URN = {urn:nbn:de:0030-drops-181081}, doi = {10.4230/LIPIcs.ICALP.2023.56}, annote = {Keywords: associahedron, mixing time, mcmc, Markov chains, triangulations, quadrangulations, k-angulations, multicommodity flow, projection-restriction} }
Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)
David Eppstein, Daniel Frishberg, and William Maxwell. On the Treewidth of Hanoi Graphs. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 13:1-13:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{eppstein_et_al:LIPIcs.FUN.2021.13, author = {Eppstein, David and Frishberg, Daniel and Maxwell, William}, title = {{On the Treewidth of Hanoi Graphs}}, booktitle = {10th International Conference on Fun with Algorithms (FUN 2021)}, pages = {13:1--13:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-145-0}, ISSN = {1868-8969}, year = {2020}, volume = {157}, editor = {Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.13}, URN = {urn:nbn:de:0030-drops-127741}, doi = {10.4230/LIPIcs.FUN.2021.13}, annote = {Keywords: Hanoi graph, Treewidth, Graph separators, Kneser graph, Vertex expansion, Haven, Tensor product} }
Published in: LIPIcs, Volume 162, 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)
David Eppstein, Daniel Frishberg, and Elham Havvaei. Simplifying Activity-On-Edge Graphs. In 17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 162, pp. 24:1-24:14, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2020)
@InProceedings{eppstein_et_al:LIPIcs.SWAT.2020.24, author = {Eppstein, David and Frishberg, Daniel and Havvaei, Elham}, title = {{Simplifying Activity-On-Edge Graphs}}, booktitle = {17th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT 2020)}, pages = {24:1--24:14}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-150-4}, ISSN = {1868-8969}, year = {2020}, volume = {162}, editor = {Albers, Susanne}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SWAT.2020.24}, URN = {urn:nbn:de:0030-drops-122718}, doi = {10.4230/LIPIcs.SWAT.2020.24}, annote = {Keywords: directed acyclic graph, activity-on-edge graph, critical path, project planning, milestone minimization, graph visualization} }
Published in: LIPIcs, Volume 149, 30th International Symposium on Algorithms and Computation (ISAAC 2019)
Nil Mamano, Alon Efrat, David Eppstein, Daniel Frishberg, Michael T. Goodrich, Stephen Kobourov, Pedro Matias, and Valentin Polishchuk. New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs. In 30th International Symposium on Algorithms and Computation (ISAAC 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 149, pp. 51:1-51:21, Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2019)
@InProceedings{mamano_et_al:LIPIcs.ISAAC.2019.51, author = {Mamano, Nil and Efrat, Alon and Eppstein, David and Frishberg, Daniel and Goodrich, Michael T. and Kobourov, Stephen and Matias, Pedro and Polishchuk, Valentin}, title = {{New Applications of Nearest-Neighbor Chains: Euclidean TSP and Motorcycle Graphs}}, booktitle = {30th International Symposium on Algorithms and Computation (ISAAC 2019)}, pages = {51:1--51:21}, series = {Leibniz International Proceedings in Informatics (LIPIcs)}, ISBN = {978-3-95977-130-6}, ISSN = {1868-8969}, year = {2019}, volume = {149}, editor = {Lu, Pinyan and Zhang, Guochuan}, publisher = {Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik}, address = {Dagstuhl, Germany}, URL = {https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2019.51}, URN = {urn:nbn:de:0030-drops-115477}, doi = {10.4230/LIPIcs.ISAAC.2019.51}, annote = {Keywords: Nearest-neighbors, Nearest-neighbor chain, motorcycle graph, straight skeleton, multi-fragment algorithm, Euclidean TSP, Steiner TSP} }
Feedback for Dagstuhl Publishing