Cover Image

Efficient Algorithms and Implementations for Extracting Maximum-Size $(k,\ell)$-Sparse Subgraphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Author:	Madarasi, Péter
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry Discrete Mathematics Combinatorics
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Quadratic-Time Algorithm for the Maximum-Weight $(k, \ell)$-Sparse Subgraph Problem
by: Deák, Bence, et al.
Published: (2025)

Asymptotically faster algorithms for recognizing $(k,\ell)$-sparse graphs
by: Deák, Bence, et al.
Published: (2026)

Vertex-ordering and arc-partitioning problems
by: Borsik, Nóra A., et al.
Published: (2025)

Separable convex optimization over indegree polytopes
by: Borsik, Nóra A., et al.
Published: (2025)

On Finding All Connected Maximum-Sized Common Subgraphs in Multiple Labeled Graphs
by: Petersen, Johannes B. S., et al.
Published: (2025)

Implicit representations via the polynomial method
by: Cardinal, Jean, et al.
Published: (2026)

A New and Faster Representation for Counting Integer Points in Parametric Polyhedra
by: Gribanov, D., et al.
Published: (2023)

Maximum list $r$-colorable induced subgraphs in $kP_3$-free graphs
by: Galby, Esther, et al.
Published: (2025)

Prefix-bounded matrices
by: Borsik, Nóra A., et al.
Published: (2025)

Isomorphism Testing for Graphs Excluding Small Topological Subgraphs
by: Neuen, Daniel
Published: (2020)

Optimal Hardness of Online Algorithms for Large Common Induced Subgraphs
by: Gamarnik, David, et al.
Published: (2026)

Maximum $k$- vs. $\ell$-colourings of graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2023)

Steiner Forest for $H$-Subgraph-Free Graphs
by: Eagling-Vose, Tala, et al.
Published: (2026)

O(1)-Distortion Planar Emulators for String Graphs
by: Chang, Hsien-Chih, et al.
Published: (2025)

The Squishy Grid Problem
by: Cai, Zixi, et al.
Published: (2025)

On The Maximum Linear Arrangement Problem for Trees
by: Alemany-Puig, Lluís, et al.
Published: (2023)

Space Efficient Algorithms for Parameterised Problems
by: Akhtar, Sheikh Shakil, et al.
Published: (2025)

Palette Sparsification for Graphs with Sparse Neighborhoods
by: Dhawan, Abhishek
Published: (2024)

On Tight Robust Coresets for $k$-Medians Clustering
by: Huang, Lingxiao, et al.
Published: (2025)

Flip Distance of Triangulations of Convex Polygons / Rotation Distance of Binary Trees is NP-complete
by: Dorfer, Joseph
Published: (2026)

Hyperplanes Avoiding Problem and Integer Points Counting in Polyhedra
by: Dakhno, Grigorii, et al.
Published: (2024)

Linear-Sized Spectral Sparsifiers and the Kadison-Singer Problem
by: Paschalidis, Phevos, et al.
Published: (2023)

Thin Trees via $k$-Respecting Cut Identities
by: Daga, Mohit
Published: (2025)

On the number of $k$-mers admitting a given lexicographical minimizer
by: Ingels, Florian, et al.
Published: (2024)

Parameterized Complexity of Temporal Connected Components: Treewidth and k-Path Graphs
by: Deligkas, Argyrios, et al.
Published: (2025)

Vigemers: on the number of $k$-mers sharing the same XOR-based minimizer
by: Ingels, Florian, et al.
Published: (2026)

Bounded indegree $k$-forests problem and a faster algorithm for directed graph augmentation
by: Arkhipov, Pavel, et al.
Published: (2024)

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

Dichotomies for Maximum Matching Cut: $H$-Freeness, Bounded Diameter, Bounded Radius
by: Lucke, Felicia, et al.
Published: (2023)

A Uniformly Random Solution to Algorithmic Redistricting
by: Cai, Jin-Yi, et al.
Published: (2024)

Stable Approximation Algorithms for Dominating Set and Independent Set
by: de Berg, Mark, et al.
Published: (2024)

A Polynomial-Time Approximation Algorithm for Complete Interval Minors
by: Bourneuf, Romain, et al.
Published: (2025)

A Structural Linear-Time Algorithm for Computing the Tutte Decomposition
by: Bourneuf, Romain, et al.
Published: (2025)

A Faster Deterministic Algorithm for Mader's $\mathcal{S}$-Path Packing
by: Iwata, Satoru, et al.
Published: (2024)

A Practical Algorithm with Performance Guarantees for the Art Gallery Problem
by: Hengeveld, Simon, et al.
Published: (2020)

Algorithms for Euclidean Distance Matrix Completion: Exploiting Proximity to Triviality
by: Fomin, Fedor V., et al.
Published: (2026)

Constructive Characterization and Recognition Algorithm for Grafts with a Connected Minimum Join
by: Kita, Nanano
Published: (2025)

A Quadratic Vertex Kernel and a Subexponential Algorithm for Subset-FAST
by: Jana, Satyabrata, et al.
Published: (2025)

Algorithms and complexity for path covers of temporal DAGs: when is Dilworth dynamic?
by: Chakraborty, Dibyayan, et al.
Published: (2024)

Boosting Rectilinear Steiner Minimum Tree Algorithms with Augmented Bounding Volume Hierarchy
by: Yang, Puhan, et al.
Published: (2025)