Cover Image

Precoloring extension with demands on paths

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Das, Arun Kumar, Opler, Michal, Valla, Tomáš
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

Exact Algorithms for Distance to Unique Vertex Cover
by: Fioravantes, Foivos, et al.
Published: (2025)

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

On the complexity of global Roman domination problem in graphs
by: Reddy, Sangam Balchandar, et al.
Published: (2026)

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

Lower bounds on pure dynamic programming for connectivity problems on graphs of bounded path-width
by: Kluk, Kacper, et al.
Published: (2025)

An extension of Dembo-Hammer's reduction algorithm for the 0-1 knapsack problem
by: Yang, Yang
Published: (2025)

Frontier Space-Time Algorithms Using Only Full Memory
by: Chmel, Petr, et al.
Published: (2026)

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

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

Most Juntas Saturate the Hardcore Lemma
by: Kumar, Vinayak M.
Published: (2025)

Inapproximability of Counting Permutation Patterns
by: Opler, Michal
Published: (2026)

An Optimal Algorithm for Sorting Pattern-Avoiding Sequences
by: Opler, Michal
Published: (2024)

List Locally Surjective Homomorphisms in Hereditary Graph Classes
by: Dvořák, Pavel, et al.
Published: (2022)

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

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

The complexity of testing all properties of planar graphs, and the role of isomorphism
by: Basu, Sabyasachi, et al.
Published: (2021)

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

Linear Hashing Is Optimal
by: Jaber, Michael, et al.
Published: (2025)

On the Parameterized Complexity of Min-Sum-Radii
by: Kumar, Pankaj, et al.
Published: (2026)

Better late, then? The hardness of choosing delays to meet passenger demands in temporal graphs
by: Kutner, David C., et al.
Published: (2025)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

On the uniqueness and computation of commuting extensions
by: Koiran, Pascal
Published: (2024)

Centrality of shortest paths: Algorithms and complexity results
by: Phosavanh, Johnson, et al.
Published: (2024)

Directed st-connectivity with few paths is in quantum logspace
by: Apers, Simon, et al.
Published: (2024)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
by: Das, Avinandan
Published: (2026)

Parallel Complexity of Depth-First-Search and Maximal path in restricted graph classes
by: Chauhan, Archit, et al.
Published: (2025)

Isometric path complexity of graphs
by: Chakraborty, Dibyayan, et al.
Published: (2022)

On graphs coverable by k shortest paths
by: Dumas, Maël, et al.
Published: (2022)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
by: Greilhuber, Jakob, et al.
Published: (2025)

The Trichotomy of Regular Property Testing
by: Bathie, Gabriel, et al.
Published: (2025)

Downward self-reducibility in the total function polynomial hierarchy
by: Gajulapalli, Karthik, et al.
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

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

A Subquadratic Two-Party Communication Protocol for Minimum Cost Flow
by: Gholizadeh, Hossein, et al.
Published: (2025)

Timeline Problems in Temporal Graphs: Vertex Cover vs. Dominating Set
by: Herrmann, Anton, et al.
Published: (2025)

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

Exact Matching and Top-k Perfect Matching Parameterized by Neighborhood Diversity or Bandwidth
by: Maalouly, Nicolas El, et al.
Published: (2025)

k-SUM Hardness Implies Treewidth-SETH
by: Lampis, Michael
Published: (2025)