Copertina

Polynomial-Delay Enumeration of Large Maximal Common Independent Sets in Two Matroids and Beyond

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Kobayashi, Yasuaki, Kurita, Kazuhiro, Wasa, Kunihiro
Natura:	Preprint
Pubblicazione:	2023
Soggetti:	Combinatorics Data Structures and Algorithms
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Efficient Constant-Factor Approximate Enumeration of Minimal Subsets for Monotone Properties with Weight Constraints
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2020)

An Approximation Algorithm for $K$-best Enumeration of Minimal Connected Edge Dominating Sets with Cardinality Constraints
di: Kurita, Kazuhiro, et al.
Pubblicazione: (2022)

Enumerating Graphlets with Amortized Time Complexity Independent of Graph Size
di: Conte, Alessio, et al.
Pubblicazione: (2024)

Reconfiguration and Enumeration of Optimal Cyclic Ladder Lotteries
di: Nozaki, Yuta, et al.
Pubblicazione: (2024)

The Complexity of Maximal Common Subsequence Enumeration
di: Buzzega, Giovanni, et al.
Pubblicazione: (2025)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2023)

Finding One Local Optimum Is Easy -- but What About Two?
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2025)

On the complexity of finding a spanning even tree in a graph
di: Hanaka, Tesshu, et al.
Pubblicazione: (2024)

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs
di: Kurita, Kazuhiro, et al.
Pubblicazione: (2025)

Matroid Intersection under Minimum Rank Oracle
di: Bárász, Mihály, et al.
Pubblicazione: (2024)

Computing diverse pair of solutions for tractable SAT
di: Gima, Tatsuya, et al.
Pubblicazione: (2024)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
di: Lee, Euiwoong, et al.
Pubblicazione: (2024)

Subquadratic Submodular Maximization with a General Matroid Constraint
di: Kobayashi, Yusuke, et al.
Pubblicazione: (2024)

The Complexity of Maximal/Closed Frequent Tree Mining for Bounded Height Trees
di: Komoto, Kenta, et al.
Pubblicazione: (2026)

Enumerating all minimal hitting sets in polynomial total time
di: Wild, Marcel
Pubblicazione: (2023)

Stable Approximation Algorithms for Dominating Set and Independent Set
di: de Berg, Mark, et al.
Pubblicazione: (2024)

Polynomial-Time Approximation Schemes for Independent Packing Problems on Fractionally Tree-Independence-Number-Fragile Graphs
di: Galby, Esther, et al.
Pubblicazione: (2023)

Cuts in Graphs with Matroid Constraints
di: Banik, Aritra, et al.
Pubblicazione: (2024)

Polynomial Kernels with Reachability for Weighted $d$-Matroid Intersection
di: Huang, Chien-Chung, et al.
Pubblicazione: (2026)

Polynomial Property Testing
di: Gishboliner, Lior, et al.
Pubblicazione: (2025)

2-Layer Fan-Planarity in Polynomial Time
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2025)

Problems on Group-labeled Matroid Bases
di: Hörsch, Florian, et al.
Pubblicazione: (2024)

An algorithmic Polynomial Freiman-Ruzsa theorem
di: Castro-Silva, Davi, et al.
Pubblicazione: (2026)

Computing Tree Decompositions with Small Independence Number
di: Dallard, Clément, et al.
Pubblicazione: (2022)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
di: Srinivasan, Eshwar, et al.
Pubblicazione: (2026)

Enumeration of Bases in Matroid with Exponentially Large Ground Set
di: Nishimura, Yuki, et al.
Pubblicazione: (2025)

Automated Discovery of Branching Rules with Optimal Complexity for the Maximum Independent Set Problem
di: Gao, Xuan-Zhao, et al.
Pubblicazione: (2024)

Solving a Random Asymmetric TSP Exactly in Quasi-Polynomial Time w.h.p
di: Bell, Tolson, et al.
Pubblicazione: (2023)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
di: Majewski, Konrad, et al.
Pubblicazione: (2022)

On the Two Paths Theorem and the Two Disjoint Paths Problem
di: Humeau, Samuel, et al.
Pubblicazione: (2025)

Connected Partitions via Connected Dominating Sets
di: Niklanovits, Aikaterini, et al.
Pubblicazione: (2025)

Enumerating minimal solution sets for metric graph problems
di: Bergougnoux, Benjamin, et al.
Pubblicazione: (2023)

On the Enumeration of all Unique Paths of Recombining Trinomial Trees
di: Torres, Ethan, et al.
Pubblicazione: (2025)

Enumerating minimal dominating sets and variants in chordal bipartite graphs
di: Castelo, Emanuel, et al.
Pubblicazione: (2025)

Finding Spanning Trees with Perfect Matchings
di: Bérczi, Kristóf, et al.
Pubblicazione: (2024)

Sharp Online Hardness for Large Balanced Independent Sets
di: Dhawan, Abhishek, et al.
Pubblicazione: (2025)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
di: Bonamy, Marthe, et al.
Pubblicazione: (2020)

On the Congruency-Constrained Matroid Base
di: Liu, Siyue, et al.
Pubblicazione: (2023)

Optimising Cylindrical Algebraic Coverings for use in SMT by Solving a Set Covering Problem with Reasons
di: Babatunde, Abiola, et al.
Pubblicazione: (2026)

Output-Sensitive Enumeration of Potential Maximal Cliques in Polynomial Space
di: Brosse, Caroline, et al.
Pubblicazione: (2024)