Image de couverture de livre

Efficient Algorithms for Interdicting Facilities in Trees and Bounded Treewidth Graphs

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Abbasi, Ali, Friedman, Eli, Golubchik, Leana, Khuller, Samir, Paolieri, Marco
Format:	Preprint
Publié:	2026
Sujets:	Data Structures and Algorithms Discrete Mathematics
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Optimal Padded Decomposition For Bounded Treewidth Graphs
par: Filtser, Arnold, et autres
Publié: (2024)

Interdiction of minimum spanning trees and other matroid bases
par: Weninger, Noah, et autres
Publié: (2024)

Treewidth Parameterized by Feedback Vertex Number
par: Molter, Hendrik, et autres
Publié: (2025)

A Lower Bound on the Competitive Ratio of the Permutation Algorithm for Online Facility Assignment on a Line
par: Harada, Tsubasa
Publié: (2024)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
par: Deligkas, Argyrios, et autres
Publié: (2025)

Temporal Graph Realization With Bounded Stretch
par: Mertzios, George B., et autres
Publié: (2025)

Problems in NP can Admit Double-Exponential Lower Bounds when Parameterized by Treewidth or Vertex Cover
par: Foucaud, Florent, et autres
Publié: (2023)

Efficient Exact Resistance Distance Computation on Small-Treewidth Graphs: a Labelling Approach
par: Liao, Meihao, et autres
Publié: (2025)

Subgraph Counting in Subquadratic Time for Bounded Degeneracy Graphs
par: Paul-Pena, Daniel, et autres
Publié: (2024)

Algorithmic Results for Weak Roman Domination Problem in Graphs
par: Paul, Kaustav, et autres
Publié: (2024)

A Dichotomy Theorem for Linear Time Homomorphism Orbit Counting in Bounded Degeneracy Graphs
par: Paul-Pena, Daniel, et autres
Publié: (2022)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
par: Wang, Chen, et autres
Publié: (2024)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
par: Gahlawat, Harmender, et autres
Publié: (2025)

UAIC_Twin_Width: An Exact yet Efficient Twin-Width Algorithm
par: Arhire, Andrei, et autres
Publié: (2025)

Greediness is not always a vice: Efficient Discovery Algorithms for Assignment Problems
par: Duvignau, Romaric, et autres
Publié: (2024)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
par: de Montgolfier, Fabien, et autres
Publié: (2025)

Vital Edges for (s,t)-mincut: Efficient Algorithms, Compact Structures, and Optimal Sensitivity Oracle
par: Baswana, Surender, et autres
Publié: (2023)

Algorithms and Hardness for Geodetic Set on Tree-like Digraphs
par: Foucaud, Florent, et autres
Publié: (2026)

Revisiting Tree Isomorphism: An Algorithmic Bric-à-Brac
par: Ingels, Florian
Publié: (2023)

Bounding Width on Graph Classes of Constant Diameter
par: Dabrowski, Konrad K., et autres
Publié: (2025)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths and Cycles I: Treewidth, Pathwidth, and Grid Graphs
par: Beisegel, Jesse, et autres
Publié: (2025)

Cutwidth Bounds via Vertex Partitions
par: Amarilli, Antoine, et autres
Publié: (2025)

Pattern-Sparse Tree Decompositions in $H$-Minor-Free Graphs
par: Marx, Dániel, et autres
Publié: (2026)

Finding d-Cuts in Graphs of Bounded Diameter, Graphs of Bounded Radius and H-Free Graphs
par: Lucke, Felicia, et autres
Publié: (2024)

Nearly Tight Bounds on Testing of Metric Properties
par: Bao, Yiqiao, et autres
Publié: (2024)

Bounding $\varepsilon$-scatter dimension via metric sparsity
par: Bourneuf, Romain, et autres
Publié: (2024)

Unsplittable Cost Flows from Unweighted Error-Bounded Variants
par: Swamy, Chaitanya, et autres
Publié: (2025)

Online Graph Coloring for $k$-Colorable Graphs
par: Kawarabayashi, Ken-ichi, et autres
Publié: (2025)

Approximation Algorithms for Optimal Hopsets
par: Dinitz, Michael, et autres
Publié: (2025)

Algorithmic Aspects of Temporal Betweenness
par: Buß, Sebastian, et autres
Publié: (2020)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
par: Yang, Puhan, et autres
Publié: (2025)

Density Matters: A Complexity Dichotomy of Deleting Edges to Bound Subgraph Density
par: Bentert, Matthias, et autres
Publié: (2026)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
par: Gaikwad, Ajinkya
Publié: (2025)

Maximizing a Submodular Function with Bounded Curvature under an Unknown Knapsack Constraint
par: Klimm, Max, et autres
Publié: (2022)

Greedy Algorithms for Shortcut Sets and Hopsets
par: Bals, Ben, et autres
Publié: (2025)

Strong Conflict-Free Vertex-Connection via Twin Cover: Kernelization and Chromatic Bounds
par: German, Samuel
Publié: (2026)

Minimum Sum Set Cover: Structures and Algorithm
par: Zhang, Zhongyi, et autres
Publié: (2026)

Terminal Steiner tree problem : Complexity and Algorithms
par: S, Jyothish, et autres
Publié: (2026)

An Effective Branch-and-Bound Algorithm with New Bounding Methods for the Maximum $s$-Bundle Problem
par: Xue, Jinghui, et autres
Publié: (2024)

An Approximation Algorithm for Monotone Submodular Cost Allocation
par: Mizutani, Ryuhei
Publié: (2025)