Cover Image

Tight Parameterized (In)tractability of Layered Crossing Minimization: Subexponential Algorithms and Kernelization

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Fomin, Fedor V., Golovach, Petr A., Inamdar, Tanmay, Saurabh, Saket, Zehavi, Meirav
Format:	Preprint
Published:	2025
Subjects:	Data Structures and Algorithms Computational Geometry
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Parameterized Geometric Graph Modification with Disk Scaling
by: Fomin, Fedor V., et al.
Published: (2024)

Hybrid k-Clustering: Blending k-Median and k-Center
by: Fomin, Fedor V., et al.
Published: (2024)

Subexponential Parameterized Algorithms for Hitting Subgraphs
by: Lokshtanov, Daniel, et al.
Published: (2024)

A Framework for Parameterized Subexponential-Subcubic-Time Algorithms for Weighted Problems in Planar Graphs
by: Bentert, Matthias, et al.
Published: (2026)

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

Tight Approximation and Kernelization Bounds for Vertex-Disjoint Shortest Paths
by: Bentert, Matthias, et al.
Published: (2024)

Exponential-Time Approximation (Schemes) for Vertex-Ordering Problems
by: Bentert, Matthias, et al.
Published: (2025)

When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
by: Bentert, Matthias, et al.
Published: (2025)

Cuts in Graphs with Matroid Constraints
by: Banik, Aritra, et al.
Published: (2024)

FPT Approximations for Connected Maximum Coverage
by: Inamdar, Tanmay, et al.
Published: (2026)

Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
by: Lokshtanov, Daniel, et al.
Published: (2024)

Stability in Graphs with Matroid Constraints
by: Fomin, Fedor V., et al.
Published: (2024)

Fixed-Parameter Tractability of Hedge Cut
by: Fomin, Fedor V., et al.
Published: (2024)

Dimension-Free Parameterized Approximation Schemes for Hybrid Clustering
by: Gadekar, Ameet, et al.
Published: (2025)

Polynomial Kernels for Spanning Tree with Diversity Requirements
by: Golovach, Petr A., et al.
Published: (2026)

Algorithmic Extensions of Dirac's Theorem
by: Fomin, Fedor V., et al.
Published: (2020)

The Parameterized Complexity Landscape of Two-Sets Cut-Uncut
by: Bentert, Matthias, et al.
Published: (2024)

On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
by: Bhore, Sujoy, et al.
Published: (2025)

Learning Small Decision Trees with Few Outliers: A Parameterized Perspective
by: Gahlawat, Harmender, et al.
Published: (2025)

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

Clustering Permutations under the Ulam Metric: A Parameterized Complexity Study
by: Bai, Tian, et al.
Published: (2026)

FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
by: Bandyapadhyay, Sayan, et al.
Published: (2023)

Exact Algorithms for Clustered Planarity with Linear Saturators
by: Da Lozzo, Giordano, et al.
Published: (2024)

(Almost-)Optimal FPT Algorithm and Kernel for $T$-Cycle on Planar Graphs
by: Gahlawat, Harmender, et al.
Published: (2025)

Packing Short Cycles
by: Bentert, Matthias, et al.
Published: (2024)

Treewidth Parameterized by Feedback Vertex Number
by: Molter, Hendrik, et al.
Published: (2025)

A Parameterized Perspective on Uniquely Restricted Matchings
by: Chaudhary, Juhi, et al.
Published: (2025)

Parameterized Analysis of Bribery in Challenge the Champ Tournaments
by: Chaudhary, Juhi, et al.
Published: (2024)

When does FTP become FPT?
by: Bentert, Matthias, et al.
Published: (2025)

Edge Clique Partition and Cover Beyond Independence
by: Fomin, Fedor V., et al.
Published: (2025)

Fault-Tolerant Matroid Bases
by: Bentert, Matthias, et al.
Published: (2025)

Clustering under Constraints: Efficient Parameterized Approximation Schemes
by: Bhore, Sujoy, et al.
Published: (2025)

A Tight Subexponential-time Algorithm for Two-Page Book Embedding
by: Ganian, Robert, et al.
Published: (2024)

Subexponential Algorithms for Clique Cover on Unit Disk and Unit Ball Graphs
by: Koana, Tomohiro, et al.
Published: (2024)

Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
by: Inamdar, Tanmay, et al.
Published: (2024)

Computing Tree Decompositions with Small Independence Number
by: Dallard, Clément, et al.
Published: (2022)

H-Planarity and Parametric Extensions: when Modulators Act Globally
by: Fomin, Fedor V., et al.
Published: (2025)

Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
by: Lokshtanov, Daniel, et al.
Published: (2024)

Minimum Temporal Spanners in Happy Graphs
by: Casteigts, Arnaud, et al.
Published: (2026)

Path Contraction Faster than $2^n$
by: Agrawal, Akanksha, et al.
Published: (2025)