Buchumschlag

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Bodlaender, Hans L., Fomin, Fedor V., Korhonen, Tuukka
Format:	Preprint
Veröffentlicht:	2025
Schlagworte:	Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Fixed-Parameter Tractability of Hedge Cut
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Finding large sparse induced subgraphs in graphs of small (but not very small) tree-independence number
von: Lokshtanov, Daniel, et al.
Veröffentlicht: (2026)

Stability in Graphs with Matroid Constraints
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

Dynamic Treewidth in Logarithmic Time
von: Korhonen, Tuukka
Veröffentlicht: (2025)

Computing Tree Decompositions with Small Independence Number
von: Dallard, Clément, et al.
Veröffentlicht: (2022)

Linear-Time Algorithms for k-Edge-Connected Components, k-Lean Tree Decompositions, and More
von: Korhonen, Tuukka
Veröffentlicht: (2024)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
von: Bonamy, Marthe, et al.
Veröffentlicht: (2022)

QPTAS for MWIS and finding large sparse induced subgraphs in graphs with few independent long holes
von: Bonnet, Édouard, et al.
Veröffentlicht: (2026)

Connectivity augmentation is fixed-parameter tractable
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2026)

Finding subdigraphs in digraphs of bounded directed treewidth
von: Lopes, Raul, et al.
Veröffentlicht: (2025)

The Leafed Induced Subtree in chordal and bounded treewidth graphs
von: Baste, Julien
Veröffentlicht: (2023)

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
von: Chudnovsky, Maria, et al.
Veröffentlicht: (2024)

Packing Short Cycles
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

A customizable inexact subgraph matching algorithm for attributed graphs
von: Benko, Tatyana, et al.
Veröffentlicht: (2025)

Minor Containment and Disjoint Paths in almost-linear time
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

Almost-linear time parameterized algorithm for rankwidth via dynamic rankwidth
von: Korhonen, Tuukka, et al.
Veröffentlicht: (2024)

An improved spectral lower bound of treewidth
von: Gima, Tatsuya, et al.
Veröffentlicht: (2024)

Dynamic Meta-Kernelization
von: Bertram, Christian, et al.
Veröffentlicht: (2025)

List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
von: Esmer, Barış Can, et al.
Veröffentlicht: (2022)

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

Separator Theorem for Minor-Free Graphs in Linear Time
von: Bonnet, Édouard, et al.
Veröffentlicht: (2025)

Compression with wildcards: All induced metric subgraphs
von: Wild, Marcel
Veröffentlicht: (2024)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
von: Bentert, Matthias, et al.
Veröffentlicht: (2026)

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
von: Foucaud, Florent, et al.
Veröffentlicht: (2025)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Algorithmic Extensions of Dirac's Theorem
von: Fomin, Fedor V., et al.
Veröffentlicht: (2020)

Fair densest subgraph across multiple graphs
von: Arachchi, Chamalee Wickrama, et al.
Veröffentlicht: (2025)

Testing H-freeness on sparse graphs, the case of bounded expansion
von: Humeau, Samuel, et al.
Veröffentlicht: (2025)

Distributed Model Checking on Graphs of Bounded Treedepth
von: Fomin, Fedor V., et al.
Veröffentlicht: (2024)

On Stable Cutsets in General and Minimum Degree Constrained Graphs
von: Vroon, Mats, et al.
Veröffentlicht: (2025)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
von: Galby, Esther, et al.
Veröffentlicht: (2025)

Finding maximum matchings in RDV graphs efficiently
von: Biedl, Therese, et al.
Veröffentlicht: (2024)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Clique-free t-matchings in degree-bounded graphs
von: Paluch, Katarzyna, et al.
Veröffentlicht: (2024)

Simple and efficient four-cycle counting on sparse graphs
von: Burkhardt, Paul, et al.
Veröffentlicht: (2023)

When does FTP become FPT?
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

Edge Clique Partition and Cover Beyond Independence
von: Fomin, Fedor V., et al.
Veröffentlicht: (2025)

Fault-Tolerant Matroid Bases
von: Bentert, Matthias, et al.
Veröffentlicht: (2025)

The problem of computing a $2$-T-connected spanning subgraph with minimum number of edges in directed graphs
von: Jaberi, Raed, et al.
Veröffentlicht: (2024)