:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Monti, Angelo, Sinaimeri, Blerina
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2409.14783
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Effects of graph operations on star pairwise compatibility graphs
by: Monti, Angelo, et al.
Published: (2024)

On star-$k$-PCGs: Exploring class boundaries for small $k$ values
by: Monti, Angelo, et al.
Published: (2022)

On Generalizations of Pairwise Compatibility Graphs
by: Calamoneri, Tiziana, et al.
Published: (2021)

Communication Complexity of Disjointness under Product Distributions
by: Hunter, Zach, et al.
Published: (2026)

Edge-Disjoint Paths in Eulerian Digraphs
by: Cavallaro, Dario, et al.
Published: (2024)

Parameterized Maximum Node-Disjoint Paths
by: Lampis, Michael, et al.
Published: (2024)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

On the Approximability of Train Routing and the Min-Max Disjoint Paths Problem
by: Bhaskar, Umang, et al.
Published: (2025)

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

Rapidly mixing loop representation quantum Monte Carlo for Heisenberg models on star-like bipartite graphs
by: Takahashi, Jun, et al.
Published: (2024)

Induced Disjoint Paths Without an Induced Minor
by: Aboulker, Pierre, et al.
Published: (2025)

On the complexity of covering points by guillotine cuts
by: Garijo, Delia, et al.
Published: (2026)

The geodesic cover problem for butterfly networks
by: Manuel, Paul, et al.
Published: (2022)

BBK: a simpler, faster algorithm for enumerating maximal bicliques in large sparse bipartite graphs
by: Baudin, Alexis, et al.
Published: (2024)

A (1.999999)-approximation ratio for vertex cover problem
by: Zohrehbandian, Majid
Published: (2024)

Structural properties of distance-bounded phylogenetic reconciliation
by: Antony, Cyriac, et al.
Published: (2026)

The proper conflict-free $k$-coloring problem and the odd $k$-coloring problem are NP-complete on bipartite graphs
by: Ahn, Jungho, et al.
Published: (2022)

On the approximability of graph visibility problems
by: Bilò, Davide, et al.
Published: (2024)

Approximate cycle double cover
by: Ghanbari, Babak, et al.
Published: (2025)

Between proper and square coloring of planar graphs, hardness and extremal graphs
by: Delépine, Thomas
Published: (2026)

Agreement theorems for high dimensional expanders in the small soundness regime: the role of covers
by: Dikstein, Yotam, et al.
Published: (2023)

Sensitivity and Hamming graphs
by: Asensio, Sara, et al.
Published: (2025)

Canonization of a random circulant graph by counting walks
by: Verbitsky, Oleg, et al.
Published: (2023)

On the complexity of embedding in graph products
by: Biedl, Therese, et al.
Published: (2023)

Proportionally dense subgraphs of maximum size in degree-constrained graphs
by: Baghirova, Narmina, et al.
Published: (2024)

Polynomial and analytic methods for classifying complexity of planar graph homomorphisms
by: Cai, Jin-Yi, et al.
Published: (2024)

Canonization of a random graph by two matrix-vector multiplications
by: Verbitsky, Oleg, et al.
Published: (2023)

Dichotomies for \#CSP on graphs that forbid a clique as a minor
by: Meng, Boning, et al.
Published: (2025)

Smaller Depth-2 Linear Circuits for Disjointness Matrices
by: Ye, Lixi
Published: (2026)

Simple inexpensive vertex and edge invariants distinguishing dataset strongly regular graphs
by: Duda, Jarek
Published: (2024)

Monitoring graph edges via shortest paths: computational complexity and approximation algorithms
by: Colli, Giordano
Published: (2025)

Determining unit distance graphs with coordinates in $\mathbb{Z}^2$ is NP-complete
by: Binnendyk, Eric
Published: (2025)

The Borsuk number of a graph
by: Cáceres, José, et al.
Published: (2026)

Optimization of a Quantum Subset Sum Oracle
by: Benoit, Angelo, et al.
Published: (2024)

$C_{2k+1}$-coloring of bounded-diameter graphs
by: Piecyk, Marta
Published: (2024)

Quantum embedding of graphs for subgraph counting
by: Adhikari, Bibhas
Published: (2026)

A parameterized algorithm for $K_r$-factors in graphs of high minimum degree
by: Gan, Luyining, et al.
Published: (2023)

Hardness of monadic second-order formulae over succinct graphs
by: Gamard, Guilhem, et al.
Published: (2023)

Combinatorial refinement on circulant graphs
by: Kluge, Laurence
Published: (2022)

Non-crossing $H$-graphs: a generalization of proper interval graphs admitting FPT algorithms
by: Bonomo-Braberman, Flavia, et al.
Published: (2025)