:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Feige, Uriel, Grinberg, Vadim
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms
Online Access:	https://arxiv.org/abs/2506.02952
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Lettericity of graphs: an FPT algorithm and a bound on the size of obstructions
by: Alecu, Bogdan, et al.
Published: (2024)

Large cliques and large independent sets: can they coexist?
by: Feige, Uriel, et al.
Published: (2025)

A characterization of one-sided error testable graph properties in bounded degeneracy graphs
by: Lachish, Oded, et al.
Published: (2026)

Testing $C_k$-freeness in bounded-arboricity graphs
by: Eden, Talya, et al.
Published: (2024)

The Leafed Induced Subtree in chordal and bounded treewidth graphs
by: Baste, Julien
Published: (2023)

Exact recovery of planted cliques in semi-random graphs
by: Khanna, Yash
Published: (2020)

Finding sparse induced subgraphs on graphs of bounded induced matching treewidth
by: Bodlaender, Hans L., et al.
Published: (2025)

Faster diameter computation in graphs of bounded Euler genus
by: Kluk, Kacper, et al.
Published: (2025)

Planted clique recovery in random geometric graphs
by: Avrachenkov, Konstantin, et al.
Published: (2025)

Reconstruction of geometric random graphs with the Simple algorithm
by: Stegehuis, Clara, et al.
Published: (2024)

Pre-assignment problem for unique minimum vertex cover on bounded clique-width graphs
by: An, Shinwoo, et al.
Published: (2024)

Testing H-freeness on sparse graphs, the case of bounded expansion
by: Humeau, Samuel, et al.
Published: (2025)

Lower bounds for graph reconstruction with maximal independent set queries
by: Michel, Lukas, et al.
Published: (2024)

Fixed-magnetization Ising on random graphs up to reconstruction
by: Gheissari, Reza, et al.
Published: (2025)

Making an oriented graph acyclic using inversions of bounded or prescribed size
by: Bang-Jensen, Jørgen, et al.
Published: (2025)

Packing $K_r$s in bounded degree graphs
by: McKay, Michael, et al.
Published: (2022)

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

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

Sparse induced subgraphs in $P_7$-free graphs of bounded clique number
by: Chudnovsky, Maria, et al.
Published: (2024)

Sparse graphs with bounded induced cycle packing number have logarithmic treewidth
by: Bonamy, Marthe, et al.
Published: (2022)

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
by: Bencs, Ferenc, et al.
Published: (2025)

On $G^p$-unimodality of radius functions in graphs: structure and algorithms
by: Chalopin, Jérémie, et al.
Published: (2025)

Clique-free t-matchings in degree-bounded graphs
by: Paluch, Katarzyna, et al.
Published: (2024)

Quantum algorithms and lower bounds for eccentricity, radius, and diameter in undirected graphs
by: Wesołowski, Adam, et al.
Published: (2025)

Upper and Lower Bounds on the Smoothed Complexity of the Simplex Method
by: Huiberts, Sophie, et al.
Published: (2022)

Two New Upper Bounds for the Maximum k-plex Problem
by: Zheng, Jiongzhi, et al.
Published: (2023)

Subsequences With Generalised Gap Constraints: Upper and Lower Complexity Bounds
by: Manea, Florin, et al.
Published: (2024)

An Almost-Optimal Upper Bound on the Push Number of the Torus Puzzle
by: Caporrella, Matteo, et al.
Published: (2026)

Oblivious Algorithms for Maximum Directed Cut: New Upper and Lower Bounds
by: Hwang, Samuel, et al.
Published: (2024)

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

Height-bounded Lempel-Ziv encodings
by: Bannai, Hideo, et al.
Published: (2024)

Quasi-linear distance query reconstruction for graphs of bounded treelength
by: Bastide, Paul, et al.
Published: (2024)

Optimal bounds on a tree inference algorithm
by: Gardiner, Jack, et al.
Published: (2024)

Improved bounds for group testing in arbitrary hypergraphs
by: De Bonis, Annalisa
Published: (2024)

A basic lower bound for property testing
by: Fischer, Eldar
Published: (2024)

Differentially private graph coloring
by: Xie, Michael, et al.
Published: (2026)

Optimal local certification on graphs of bounded pathwidth
by: Baterisna, Dan Alden, et al.
Published: (2025)

Enumerating minimal dominating sets in the (in)comparability graphs of bounded dimension posets
by: Bonamy, Marthe, et al.
Published: (2020)

Pseudorandom Hashing for Space-bounded Computation with Applications in Streaming
by: Kacham, Praneeth, et al.
Published: (2023)

Tight bounds for the sensitivity of CDAWGs with left-end edits
by: Fujimaru, Hiroto, et al.
Published: (2023)