Buchumschlag

On the Complexity of Hyperpath and Minimal Separator Enumeration in Directed Hypergraphs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Kurita, Kazuhiro, Mann, Kevin
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

The Complexity of Maximal Common Subsequence Enumeration
von: Buzzega, Giovanni, et al.
Veröffentlicht: (2025)

Finding One Local Optimum Is Easy -- but What About Two?
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2025)

The Complexity of Counting Small Sub-Hypergraphs
von: Bressan, Marco, et al.
Veröffentlicht: (2025)

Local Enumeration: The Not-All-Equal Case
von: Gurumukhani, Mohit, et al.
Veröffentlicht: (2025)

Novel Complexity Results for Temporal Separators with Deadlines
von: Dondi, Riccardo, et al.
Veröffentlicht: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
von: Liu, Yang P., et al.
Veröffentlicht: (2026)

Complexity of Finding and Enumerating Interconnection Trees
von: Demange, Noé, et al.
Veröffentlicht: (2026)

On the Complexity of Minimizing Energy Consumption of Partitioning DAG Tasks
von: Liu, Wei, et al.
Veröffentlicht: (2024)

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

From Amortized to Worst Case Delay in Enumeration Algorithms
von: Capelli, Florent, et al.
Veröffentlicht: (2021)

Enumerating minimal vertex covers and dominating sets with capacity and/or connectivity constraints
von: Kobayashi, Yasuaki, et al.
Veröffentlicht: (2023)

Emit As You Go: Enumerating Edges of a Spanning Tree
von: Casel, Katrin, et al.
Veröffentlicht: (2025)

Enumerating models of DNF faster: breaking the dependency on the formula size
von: Capelli, Florent, et al.
Veröffentlicht: (2018)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
von: Grandjean, Étienne, et al.
Veröffentlicht: (2025)

The Parameterized Complexity of Scheduling with Precedence Delays: Shuffle Product and Directed Bandwidth
von: Bodlaender, Hans L., et al.
Veröffentlicht: (2026)

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

Improved Hardness and Approximations for Cardinality-Based Minimum $s$-$t$ Cuts Problems in Hypergraphs
von: Adriaens, Florian, et al.
Veröffentlicht: (2024)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Hypergraph Samplers: Typical and Worst Case Behavior
von: Alev, Vedat Levi, et al.
Veröffentlicht: (2026)

Size Minimization For Multi-Output AND-Functions
von: Armbruster, Susanne
Veröffentlicht: (2024)

A Fast Coloring Oracle for Average Case Hypergraphs
von: Marcussen, Cassandra, et al.
Veröffentlicht: (2025)

Minimizing Envy and Maximizing Happiness in Graphical House Allocation
von: Dhar, Anubhav, et al.
Veröffentlicht: (2025)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

The Robotaxi Placement Problem: Minimizing Expected ETA for Stochastic Demand
von: Caragiannis, Ioannis, et al.
Veröffentlicht: (2026)

Connectivity-Preserving Important Separators: A Framework for Cut-Uncut Problems
von: Kenig, Batya
Veröffentlicht: (2025)

Faster Algorithms for Sparse ILP and Hypergraph Multi-Packing/Multi-Cover Problems
von: Gribanov, Dmitry, et al.
Veröffentlicht: (2022)

Parameterized Complexity of Vehicle Routing
von: Döring, Michelle, et al.
Veröffentlicht: (2025)

The Complexity of Finding and Counting Subtournaments
von: Döring, Simon, et al.
Veröffentlicht: (2025)

On the Parameterized Complexity of Odd Coloring
von: Bhyravarapu, Sriram, et al.
Veröffentlicht: (2025)

On the Complexity of Signed Roman Domination
von: Reddy, Sangam Balchandar
Veröffentlicht: (2025)

On the Space Complexity of Online Convolution
von: Andersson, Joel Daniel, et al.
Veröffentlicht: (2025)

Computational Complexity in Property Testing
von: Pinto Jr., Renato Ferreira, et al.
Veröffentlicht: (2025)

PLS-complete problems with lexicographic cost functions: Max-$k$-SAT and Abelian Permutation Orbit Minimization
von: Scheder, Dominik, et al.
Veröffentlicht: (2025)

The Fine-Grained Complexity of Episode Matching
von: Bille, Philip, et al.
Veröffentlicht: (2021)

On the Parameterized Complexity of Min-Sum-Radii
von: Kumar, Pankaj, et al.
Veröffentlicht: (2026)

A Space-space Trade-off for Directed st-Connectivity
von: Edenhofer, Roman
Veröffentlicht: (2026)

Complexity of Local Search for Euclidean Clustering Problems
von: Manthey, Bodo, et al.
Veröffentlicht: (2023)

The Query Complexity of Local Search and Brouwer in Rounds
von: Brânzei, Simina, et al.
Veröffentlicht: (2020)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
von: Chudigiewitsch, Florian, et al.
Veröffentlicht: (2026)

Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
von: Levet, Michael, et al.
Veröffentlicht: (2025)