Copertina

Polynomial-time approximation schemes for induced subgraph problems on fractionally tree-independence-number-fragile graphs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Galby, Esther, Munaro, Andrea, Yang, Shizhou
Natura:	Preprint
Pubblicazione:	2024
Soggetti:	Data Structures and Algorithms Computational Geometry Combinatorics 05C85, 05C75, 05C62, 68W25
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

Layered tree-independence number and clique-based separators
di: Dallard, Clément, et al.
Pubblicazione: (2025)

Treewidth versus clique number. IV. Tree-independence number of graphs excluding an induced star
di: Dallard, Clément, et al.
Pubblicazione: (2024)

On algorithmic applications of sim-width and mim-width of $(H_1, H_2)$-free graphs
di: Munaro, Andrea, et al.
Pubblicazione: (2022)

Critical Relaxed-Stable Matchings with Ties in the Many-to-Many Setting
di: Nasre, Meghana, et al.
Pubblicazione: (2023)

Zero-free regions of partition functions with applications to algorithms and graph limits
di: Regts, Guus
Pubblicazione: (2015)

$t$-sails and sparse hereditary classes of unbounded tree-width
di: Cocks, Daniel
Pubblicazione: (2023)

On $γ$-Contraction and $β$-Contraction: A Unified Framework for Colour-Preserving Graph Reduction
di: Onofri, Elia
Pubblicazione: (2024)

Tree independence number V. Walls and claws
di: Chudnovsky, Maria, et al.
Pubblicazione: (2025)

Dynamic programming on bipartite tree decompositions
di: Jaffke, Lars, et al.
Pubblicazione: (2023)

A tame vs. feral dichotomy for graph classes excluding an induced minor or induced topological minor
di: Milanič, Martin, et al.
Pubblicazione: (2024)

Excluding an induced wheel minor in graphs without large induced stars
di: Choi, Mujin, et al.
Pubblicazione: (2025)

Finding irrelevant vertices in linear time on bounded-genus graphs
di: Golovach, Petr A., et al.
Pubblicazione: (2019)

Shortest two disjoint paths in conservative graphs
di: Schlotter, Ildikó
Pubblicazione: (2023)

Young domination on Hamming rectangles
di: Gravner, Janko, et al.
Pubblicazione: (2025)

Polynomial-size encoding of all cuts of small value in integer-valued symmetric submodular functions
di: Oum, Sang-il, et al.
Pubblicazione: (2026)

W-state graphs: Structure and Algorithms
di: Gajjala, Rishikesh, et al.
Pubblicazione: (2026)

Graph modification of bounded size to minor-closed classes as fast as vertex deletion
di: Morelle, Laure, et al.
Pubblicazione: (2025)

Obstructions to Erdős-Pósa Dualities for Minors
di: Paul, Christophe, et al.
Pubblicazione: (2024)

A Simple 2-Approximation for Maximum-Leaf Spanning Tree
di: Liao, I-Cheng, et al.
Pubblicazione: (2023)

Faster parameterized algorithms for modification problems to minor-closed classes
di: Morelle, Laure, et al.
Pubblicazione: (2022)

Minimal obstructions to $C_5$-coloring in hereditary graph classes
di: Goedgebeur, Jan, et al.
Pubblicazione: (2024)

Improved Approximation Algorithms for Path and Forest Augmentation via a Novel Relaxation
di: Hommelsheim, Felix
Pubblicazione: (2025)

A $4/3$ Approximation for $2$-Vertex-Connectivity
di: Bosch-Calvo, Miguel, et al.
Pubblicazione: (2023)

Parameterizing the quantification of CMSO: model checking on minor-closed graph classes
di: Sau, Ignasi, et al.
Pubblicazione: (2024)

Cluster Before You Hallucinate: Approximating Node-Capacitated Network Design and Energy Efficient Routing
di: Krishnaswamy, Ravishankar, et al.
Pubblicazione: (2014)

A Constant-factor Approximation for Weighted Bond Cover
di: Kim, Eun Jung, et al.
Pubblicazione: (2021)

Pathographs and some (un)decidability results
di: Carter, Daniel, et al.
Pubblicazione: (2025)

Awesome graph parameters
di: Štorgel, Kenny Bešter, et al.
Pubblicazione: (2025)

Colorful Minors
di: Protopapas, Evangelos, et al.
Pubblicazione: (2025)

A $5/4$-Approximation for Two-Edge Connectivity
di: Bosch-Calvo, Miguel, et al.
Pubblicazione: (2024)

Vertex identification to a forest
di: Morelle, Laure, et al.
Pubblicazione: (2024)

Blazing a Trail via Matrix Multiplications: A Faster Algorithm for Non-shortest Induced Paths
di: Chiu, Yung-Chung, et al.
Pubblicazione: (2021)

Tree decompositions meet induced matchings: beyond Max Weight Independent Set
di: Lima, Paloma T., et al.
Pubblicazione: (2024)

Finding cliques and dense subgraphs using edge queries
di: Csóka, Endre, et al.
Pubblicazione: (2023)

Branch-width of connectivity functions is fixed-parameter tractable
di: Korhonen, Tuukka, et al.
Pubblicazione: (2026)

Tree-independence number VI. Thetas and pyramids
di: Chudnovsky, Maria, et al.
Pubblicazione: (2025)

On the joint embedding property for cographs and trees
di: Carter, Daniel
Pubblicazione: (2024)

The Upper Clique Transversal Problem
di: Milanič, Martin, et al.
Pubblicazione: (2023)

Perfect phylogenies via the Minimum Uncovering Branching problem: efficiently solvable cases
di: Baghirova, Narmina, et al.
Pubblicazione: (2025)

Polynomial $χ$-boundedness for excluding $P_5$
di: Nguyen, Tung H.
Pubblicazione: (2025)