Cover Image

Proportionally dense subgraphs of maximum size in degree-constrained graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Baghirova, Narmina, Castillon, Antoine
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Graphs without a partition into two proportionally dense subgraphs
by: Bazgan, Cristina, et al.
Published: (2018)

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

Finding large $k$-colorable induced subgraphs in (bull, chair)-free and (bull,E)-free graphs
by: Hodur, Nadzieja, et al.
Published: (2025)

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

Perfect phylogenies via the Minimum Uncovering Branching problem: efficiently solvable cases
by: Baghirova, Narmina, et al.
Published: (2025)

A lower bound on the field size of convolutional codes with a maximum distance profile and an improved construction
by: Chen, Zitan
Published: (2023)

The complexity of finding and enumerating optimal subgraphs to represent spatial correlation
by: Enright, Jessica, et al.
Published: (2020)

On the instance optimality of detecting collisions and subgraphs
by: Ben-Eliezer, Omri, et al.
Published: (2023)

A sublinear query quantum algorithm for s-t minimum cut on dense simple graphs
by: Apers, Simon, et al.
Published: (2021)

A note on approximating the average degree of bounded arboricity graphs
by: Eden, Talya, et al.
Published: (2026)

Rational degree is polynomially related to degree
by: Kothari, Robin, et al.
Published: (2026)

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

On hardness of computing analytic Brouwer degree
by: Chakraborty, Somnath
Published: (2023)

Equations over Finite Monoids with Infinite Promises
by: Larrauri, Alberto, et al.
Published: (2025)

Disjoint covering of bipartite graphs with $s$-clubs
by: Monti, Angelo, et al.
Published: (2024)

Low-degree approximation of QAC$^0$ circuits
by: Montanaro, Ashley, et al.
Published: (2024)

Critical window for approximate counting in dense Ising models
by: Galanis, Andreas, et al.
Published: (2026)

Indefiniteness makes lattice reduction easier
by: Joux, Antoine
Published: (2025)

A sharp interaction-degree threshold for simulating QAOA
by: Āboliņš, Ralfs, et al.
Published: (2026)

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

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

Proper colorings of a graph in linear time using a number of colors linear in the maximum degree of the graph
by: Bhandari, Kritika, et al.
Published: (2025)

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

Hardness of Learning Boolean Functions from Label Proportions
by: Guruswami, Venkatesan, 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)

Bounded degree QBF and positional games
by: Oijid, Nacim
Published: (2024)

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

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)

Low-degree learning and the metric entropy of polynomials
by: Eskenazis, Alexandros, et al.
Published: (2022)

Testing noisy low-degree polynomials for sparsity
by: Bao, Yiqiao, et al.
Published: (2025)

Maximizing Minimum Cycle Bases Intersection
by: Watel, Dimitri, et al.
Published: (2024)

On the degree of polynomials computing square roots mod p
by: Kedlaya, Kiran, et al.
Published: (2023)

A degree 4 sum-of-squares lower bound for the clique number of the Paley graph
by: Kunisky, Dmitriy, et al.
Published: (2022)

Finding dense sub-lattices as low-energy states of a Hamiltonian
by: Barberà-Rodríguez, Júlia, et al.
Published: (2023)

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

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