Parameterized complexity of maximum edge colorable subgraph

DOI10.1007/s00453-022-01003-0OpenAlexW3075687921WikidataQ114229325 ScholiaQ114229325MaRDI QIDQ2088595

Abhishek Sahu, Madhumita Kundu, Akanksha Agrawal, Saket Saurabh, Prafullkumar Tale

Publication date: 6 October 2022

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s00453-022-01003-0

zbMATH Keywords

edge coloringkernelizationFPT algorithmskernel lower bound

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Parameterized complexity, tractability and kernelization (68Q27)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Improved upper bounds for vertex cover
• Graph edge coloring: a survey
• Parameterized algorithms and kernels for rainbow matching
• Classifying \(k\)-edge colouring for \(H\)-free graphs
• Integer Programming with a Fixed Number of Variables
• Randomized Divide-and-Conquer: Improved Path, Matching, and Packing Algorithms
• Minkowski's Convex Body Theorem and Integer Programming
• The NP-Completeness of Edge-Coloring
• Color-coding
• Kernelization
• NP completeness of finding the chromatic index of regular graphs
• Paths to Trees and Cacti
• Sparsification Upper and Lower Bounds for Graphs Problems and Not-All-Equal SAT
• Parameterized Algorithms
• Improved Parameterized Upper Bounds for Vertex Cover

This page was built for publication: Parameterized complexity of maximum edge colorable subgraph