Copertina

List Locally Surjective Homomorphisms in Hereditary Graph Classes

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Dvořák, Pavel, Krawczyk, Monika, Masařík, Tomáš, Novotná, Jana, Rzążewski, Paweł, Żuk, Aneta
Natura:	Preprint
Pubblicazione:	2022
Soggetti:	Data Structures and Algorithms Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

U-Bubble Model for Mixed Unit Interval Graphs and its Applications: The MaxCut Problem Revisited
di: Kratochvíl, Jan, et al.
Pubblicazione: (2020)

Colouring $(P_r+P_s)$-Free Graphs
di: Klimošová, Tereza, et al.
Pubblicazione: (2018)

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

Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
di: Esmer, Barış Can, et al.
Pubblicazione: (2024)

Maximum Weight Independent Set in Hereditary Classes of Ordered Graphs
di: Bieliński, Paweł Rafał, et al.
Pubblicazione: (2026)

Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices
di: Dvořák, Pavel, et al.
Pubblicazione: (2017)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
di: Lokshtanov, Daniel, et al.
Pubblicazione: (2024)

A tight quasi-polynomial bound for Global Label Min-Cut
di: Jaffke, Lars, et al.
Pubblicazione: (2022)

On the Complexity of Establishing Hereditary Graph Properties via Vertex Splitting
di: Firbas, Alexander, et al.
Pubblicazione: (2024)

Max Weight Independent Set in graphs with no long claws: An analog of the Gyárfás' path argument
di: Majewski, Konrad, et al.
Pubblicazione: (2022)

Inclusive and Exclusive Vertex Splitting into Specific Graph Classes: NP Hardness and Algorithms
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2025)

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

Self-referential instances of the dominating set problem are irreducible
di: Zhou, Guangyan
Pubblicazione: (2026)

The Query Complexity of Local Search in Rounds on General Graphs
di: Brânzei, Simina, et al.
Pubblicazione: (2026)

A General Framework for Low Soundness Homomorphism Testing
di: Mittal, Tushant, et al.
Pubblicazione: (2025)

On 3-Coloring of $(2P_4,C_5)$-Free Graphs
di: Jelínek, Vít, et al.
Pubblicazione: (2020)

Cluster Editing on Cographs and Related Classes
di: Lafond, Manuel, et al.
Pubblicazione: (2024)

Constant Time with Minimal Preprocessing, a Robust and Extensive Complexity Class
di: Grandjean, Étienne, et al.
Pubblicazione: (2025)

Sublinear-Time Approximation for Graph Frequency Vectors in Hyperfinite Graphs
di: Moroie, Gregory
Pubblicazione: (2025)

Clustering with Locally Bounded Ignorance
di: Garvardt, Jaroslav, et al.
Pubblicazione: (2026)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
di: Döring, Simon, et al.
Pubblicazione: (2024)

Precoloring extension with demands on paths
di: Das, Arun Kumar, et al.
Pubblicazione: (2025)

Local Enumeration: The Not-All-Equal Case
di: Gurumukhani, Mohit, et al.
Pubblicazione: (2025)

Efficient Catalytic Graph Algorithms
di: Cook, James, et al.
Pubblicazione: (2025)

Complexity of Local Search for Euclidean Clustering Problems
di: Manthey, Bodo, et al.
Pubblicazione: (2023)

The Query Complexity of Local Search and Brouwer in Rounds
di: Brânzei, Simina, et al.
Pubblicazione: (2020)

Fair Vertex Problems Parameterized by Cluster Vertex Deletion
di: Masařík, Tomáš, et al.
Pubblicazione: (2025)

Neighborhood-Aware Graph Labeling Problem
di: Shahverdikondori, Mohammad, et al.
Pubblicazione: (2026)

Knapsack on Graphs with Relaxed Neighborhood Constraints
di: Dey, Palash, et al.
Pubblicazione: (2025)

Matching and Edge Cover in Temporal Graphs
di: Cioni, Lapo, et al.
Pubblicazione: (2025)

The Parameterized Landscape of Labeled Graph Contractions
di: Lafond, Manuel, et al.
Pubblicazione: (2025)

Residue Domination in Bounded-Treewidth Graphs
di: Greilhuber, Jakob, et al.
Pubblicazione: (2024)

Semi-Streaming Algorithms for Graph Property Certification
di: Das, Avinandan, et al.
Pubblicazione: (2025)

Generalized Graph Packing Problems Parameterized by Treewidth
di: Esmer, Barış Can, et al.
Pubblicazione: (2025)

Streaming Complexity Separations for Dense and Sparse Graphs
di: Liu, Yang P., et al.
Pubblicazione: (2026)

Parameterized Algorithms for Editing to Uniform Cluster Graph
di: Gaikwad, Ajinkya, et al.
Pubblicazione: (2024)

Coloring Graphs with Few Colors in the Streaming Model
di: Assadi, Sepehr, et al.
Pubblicazione: (2025)

On the Complexity of Fundamental Problems for DAG-Compressed Graphs
di: Chudigiewitsch, Florian, et al.
Pubblicazione: (2026)

Finding One Local Optimum Is Easy -- but What About Two?
di: Kobayashi, Yasuaki, et al.
Pubblicazione: (2025)

Superpolynomial smoothed complexity of 3-FLIP in Local Max-Cut
di: Michel, Lukas, et al.
Pubblicazione: (2023)