Buchumschlag

Fixed-parameter tractability and hardness for Steiner rooted and locally connected orientations

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bérczi, Kristóf, Hörsch, Florian, Imolay, András, Schwarcz, Tamás
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Discrete Mathematics
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Interaction between skew-representability, tensor products, extension properties, and rank inequalities
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Matroid products via submodular coupling
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Problems on Group-labeled Matroid Bases
von: Hörsch, Florian, et al.
Veröffentlicht: (2024)

Approximating maximum-size properly colored forests
von: Bai, Yuhang, et al.
Veröffentlicht: (2024)

A note on embracing exchange sequences in oriented matroids
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

The Rainbow Arborescence Problem on Cycles
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

Increasing arc-connectivity by bounded- and fixed-size inversions
von: Hörsch, Florian, et al.
Veröffentlicht: (2026)

Hypergraph Connectivity Augmentation in Strongly Polynomial Time
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Splitting-off in Hypergraphs
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2023)

Rainbow Arborescence Conjecture
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Approximating Submodular Matroid-Constrained Partitioning
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

A hierarchy of edge-weight symmetries in perfect matchings
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2026)

Cyclic ordering of split matroids
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

How to see the forest for the trees
von: Bérczi-Kovács, Erika, et al.
Veröffentlicht: (2025)

Maximum Reachability Orientation of Mixed Graphs
von: Hörsch, Florian
Veröffentlicht: (2025)

On approximating the rank of graph divisors
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2022)

Complexity results on the decomposition of a digraph into directed linear forests and out-stars
von: Hörsch, Florian, et al.
Veröffentlicht: (2024)

Diameter of the inversion graph
von: Havet, Frédéric, et al.
Veröffentlicht: (2024)

Inverse matroid optimization under subset constraints
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2025)

On the minimum number of inversions to make a digraph $k$-(arc-)strong
von: Duron, Julien, et al.
Veröffentlicht: (2023)

Minimum Spanning Trees with Bounded Degrees of Vertices in a Specified Stable Set
von: Brause, Christoph, et al.
Veröffentlicht: (2022)

Monotonic Decompositions of Submodular Set Functions
von: Bérczi, Kristóf, et al.
Veröffentlicht: (2024)

Families of tractable problems with respect to vertex-interval-membership width and its generalisations
von: Enright, Jessica, et al.
Veröffentlicht: (2025)

Branch-width of connectivity functions is fixed-parameter tractable
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2026)

Completely Independent Steiner Trees
von: Maheshwari, Anil, et al.
Veröffentlicht: (2026)

Beyond hypergraph acyclicity: limits of tractability for pseudo-Boolean optimization
von: Del Pia, Alberto, et al.
Veröffentlicht: (2024)

Faster algorithms for graph homomorphism via tractable constraint satisfaction
von: Carbonnel, Clément
Veröffentlicht: (2026)

On the Extension Theorem for Packing Steiner Forests
von: Zeng, Jinghan A
Veröffentlicht: (2026)

Why Districting Becomes NP-hard
von: Jost, Niklas, et al.
Veröffentlicht: (2025)

Testing popularity in linear time via maximum matching
von: Bérczi-Kovács, Erika, et al.
Veröffentlicht: (2023)

A note on hardness of promise hypergraph colouring
von: Wrochna, Marcin
Veröffentlicht: (2022)

Finding hypergraph immersion is fixed-parameter tractable
von: Meng, Xiangyi, et al.
Veröffentlicht: (2024)

Regular packing of rooted hyperforests with root constraints in hypergraphs
von: Hoppenot, Pierre, et al.
Veröffentlicht: (2023)

Internally-disjoint directed pendant Steiner trees with three terminal vertices in Cartesian product digraphs
von: Yu, Shanshan, et al.
Veröffentlicht: (2026)

On the Bidirected Cut Relaxation for Steiner Forest
von: Byrka, Jarosław, et al.
Veröffentlicht: (2024)

Graceful coloring is computationally hard
von: Antony, Cyriac, et al.
Veröffentlicht: (2024)

A Brooks-type theorem for the k-choosability of graphs with maximum local edge-connectivity k
von: Bastida, Sam, et al.
Veröffentlicht: (2026)

Algorithms and hardness for Metric Dimension on digraphs
von: Dailly, Antoine, et al.
Veröffentlicht: (2023)

Terminal Steiner tree problem : Complexity and Algorithms
von: S, Jyothish, et al.
Veröffentlicht: (2026)

Monitoring arc-geodetic sets of oriented graphs
von: Das, Tapas, et al.
Veröffentlicht: (2024)