Copertina

Sampling Unlabeled Chordal Graphs in Expected Polynomial Time

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Hébert-Johnson, Úrsula, Lokshtanov, Daniel
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Counting and Sampling Labeled Chordal Graphs in Polynomial Time
di: Hebert-Johnson, Ursula, et al.
Pubblicazione: (2023)

A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
di: S, Ajaykrishnan E, et al.
Pubblicazione: (2025)

Revisiting Token Sliding on Chordal Graphs
di: Adak, Rajat, et al.
Pubblicazione: (2025)

Cluster Vertex Deletion on Chordal Graphs
di: Cao, Yixin, et al.
Pubblicazione: (2026)

A $2\ell k$ Kernel for $\ell$-Component Order Connectivity
di: Kumar, Mithilesh, et al.
Pubblicazione: (2016)

Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
di: Kumar, Mithilesh, et al.
Pubblicazione: (2024)

Succinct Data Structure for Chordal Graphs with Bounded Vertex Leafage
di: Balakrishnan, Girish, et al.
Pubblicazione: (2024)

Breaking the Barrier $2^k$ for Subset Feedback Vertex Set in Chordal Graphs
di: Bai, Tian, et al.
Pubblicazione: (2022)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2026)

Approximation Ratio of the Min-Degree Greedy Algorithm for Maximum Independent Set on Interval and Chordal Graphs
di: Chaplick, Steven, et al.
Pubblicazione: (2024)

Tight Bounds for Chordal/Interval Vertex Deletion Parameterized by Treewidth
di: Wlodarczyk, Michal
Pubblicazione: (2023)

Parameterized Approximation for Capacitated $d$-Hitting Set with Hard Capacities
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

Odd Cycle Transversal on $P_5$-free Graphs in Polynomial Time
di: Agrawal, Akanksha, et al.
Pubblicazione: (2024)

Dynamic Connectivity with Expected Polylogarithmic Worst-Case Update Time
di: Meierhans, Simon, et al.
Pubblicazione: (2025)

FPT Approximations for Connected Maximum Coverage
di: Inamdar, Tanmay, et al.
Pubblicazione: (2026)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
di: Inamdar, Tanmay, et al.
Pubblicazione: (2024)

Fixed-Parameter Tractability of Hedge Cut
di: Fomin, Fedor V., et al.
Pubblicazione: (2024)

Faster Parameterized Vertex Multicut
di: Chu, Huairui, et al.
Pubblicazione: (2026)

Beyond Exact Fairness: Envy-Free Incomplete Connected Fair Division
di: S, Ajaykrishnan E, et al.
Pubblicazione: (2025)

Querying in Constant Expected Time with Learned Indexes
di: Croquevielle, Luis, et al.
Pubblicazione: (2024)

Tree Independence Number IV. Even-hole-free Graphs
di: Chudnovsky, Maria, et al.
Pubblicazione: (2024)

A Polynomial-Time Algorithm for the Next-to-Shortest Path Problem on Positively Weighted Directed Graphs
di: Chen, Kuowen, et al.
Pubblicazione: (2025)

Approximate Minimum Sum Colorings and Maximum $k$-Colorable Subgraphs of Chordal Graphs
di: DeHaan, Ian, et al.
Pubblicazione: (2024)

Hypergraph Unreliability in Quasi-Polynomial Time
di: Cen, Ruoxu, et al.
Pubblicazione: (2024)

Improved Lower Bounds on the Expected Length of Longest Common Subsequences
di: Heineman, George T., et al.
Pubblicazione: (2024)

Fully Dynamic Connectivity in $O(\log n(\log\log n)^2)$ Amortized Expected Time
di: Huang, Shang-En, et al.
Pubblicazione: (2016)

Edge-Minimum Walk of Modular Length in Polynomial Time
di: Amarilli, Antoine, et al.
Pubblicazione: (2024)

Sampling Balanced Forests of Grids in Polynomial Time
di: Cannon, Sarah, et al.
Pubblicazione: (2023)

Polynomial-Time Constant-Approximation for Fair Sum-of-Radii Clustering
di: Nezhad, Sina Bagheri, et al.
Pubblicazione: (2025)

Parameterized Saga of First-Fit and Last-Fit Coloring
di: Agrawal, Akanksha, et al.
Pubblicazione: (2024)

Induced Minors and Coarse Tree Decompositions
di: Chudnovsky, Maria, et al.
Pubblicazione: (2026)

A Polynomial-time Algorithm for Detecting the Possibility of Braess Paradox in Directed Graphs
di: Cenciarelli, Pietro, et al.
Pubblicazione: (2016)

Polynomial Time Learning-Augmented Algorithms for NP-hard Permutation Problems
di: Bampis, Evripidis, et al.
Pubblicazione: (2025)

Polynomial-Time Algorithms for Weaver's Discrepancy Problem in a Dense Regime
di: Jourdan, Ben, et al.
Pubblicazione: (2024)

Optimal Unlabeled Pebble Motion on Trees and its Application to Multi-Agent Path Finding
di: Calvi, Annalisa, et al.
Pubblicazione: (2026)

Robust Contraction Decomposition for Minor-Free Graphs and its Applications
di: Bandyapadhyay, Sayan, et al.
Pubblicazione: (2024)

Path Contraction Faster than $2^n$
di: Agrawal, Akanksha, et al.
Pubblicazione: (2025)

Polynomial Time Algorithms for Integer Programming and Unbounded Subset Sum in the Total Regime
di: Aggarwal, Divesh, et al.
Pubblicazione: (2024)