Cover Image

Approximating Maximum Edge 2-Coloring by Normalizing Graphs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Mömke, Tobias, Popa, Alexandru, Roshany-Tabrizi, Aida, Ruderer, Michael, Vincze, Roland
Format:	Preprint
Published:	2024
Subjects:	Discrete Mathematics Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Polynomial-time algorithms for PATH COVER and PATH PARTITION on trees and graphs of bounded treewidth
by: Foucaud, Florent, et al.
Published: (2025)

Exponential Time Approximation for Coloring 3-Colorable Graphs
by: Guruswami, Venkatesan, et al.
Published: (2024)

Randomized Greedy Online Edge Coloring Succeeds for Dense and Randomly-Ordered Graphs
by: Dudeja, Aditi, et al.
Published: (2024)

Online Graph Coloring for $k$-Colorable Graphs
by: Kawarabayashi, Ken-ichi, et al.
Published: (2025)

Approximating Prize-Collecting Variants of TSP
by: Alimi, Morteza, et al.
Published: (2024)

Maximum Biclique for Star 1,2,3 -free and Bounded Bimodularwidth Twin-free Bipartite Graphs $\star$
by: de Montgolfier, Fabien, et al.
Published: (2025)

Approximation Algorithm of Minimum All-Ones Problem for Arbitrary Graphs
by: Wang, Chen, et al.
Published: (2024)

Light Edge Fault Tolerant Graph Spanners
by: Bodwin, Greg, et al.
Published: (2025)

Graph Coloring Below Guarantees via Co-Triangle Packing
by: Akmal, Shyan, et al.
Published: (2025)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local Uniformity
by: Jain, Vishesh, et al.
Published: (2026)

An approximation algorithm for Maximum DiCut vs. Cut
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Optimal Padded Decomposition For Bounded Treewidth Graphs
by: Filtser, Arnold, et al.
Published: (2024)

Optimal Mixing for Randomly Sampling Edge Colorings on Trees Down to the Max Degree
by: Carlson, Charlie, et al.
Published: (2024)

A Dichotomy for Maximum PCSPs on Graphs
by: Nakajima, Tamio-Vesa, et al.
Published: (2024)

Weighted Clique and Independent Set in Edge-Distant Hereditary Graphs
by: Srinivasan, Eshwar, et al.
Published: (2026)

Approximate Realizations for Outerplanaric Degree Sequences
by: Bar-Noy, Amotz, et al.
Published: (2024)

Approximating Submodular Matroid-Constrained Partitioning
by: Bérczi, Kristóf, et al.
Published: (2025)

(Approximate) Matrix Multiplication via Convolutions
by: Uffenheimer, Yahel, et al.
Published: (2025)

An Approximate Generalization of the Okamura-Seymour Theorem
by: Kumar, Nikhil
Published: (2022)

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

An Approximation Algorithm for Monotone Submodular Cost Allocation
by: Mizutani, Ryuhei
Published: (2025)

A Constant-Factor Approximation for Directed Latency
by: Blauth, Jannis, et al.
Published: (2025)

Parameterized Algorithms for Balanced Cluster Edge Modification Problems
by: Madathil, Jayakrishnan, et al.
Published: (2024)

The Parameterized Complexity of Vertex-Coloring Edge-Weighting
by: Aute, Shubhada, et al.
Published: (2026)

Approximation algorithms for non-sequential star packing problems
by: Hu, Mengyuan, et al.
Published: (2024)

Approximation of Spanning Tree Congestion using Hereditary Bisection
by: Kolman, Petr
Published: (2024)

Approximately covering vertices by order-$5$ or longer paths
by: Gong, Mingyang, et al.
Published: (2024)

Determining Implication of Fixed Matrix Prenex Normal Forms Can Be Decided in Linear Time
by: Wang, Adam
Published: (2025)

Bicriterial Approximation for the Incremental Prize-Collecting Steiner-Tree Problem
by: Disser, Yann, et al.
Published: (2024)

Simultaneously Approximating All $\ell_p$-norms in Correlation Clustering
by: Davies, Sami, et al.
Published: (2023)

Parameterized Saga of First-Fit and Last-Fit Coloring
by: Agrawal, Akanksha, et al.
Published: (2024)

A Constant-Approximation Algorithm for Budgeted Sweep Coverage with Mobile Sensors
by: Liang, Wei, et al.
Published: (2024)

Approximation Algorithms for the $b$-Matching and List-Restricted Variants of MaxQAP
by: Nanta, Jiratchaphat, et al.
Published: (2025)

Total Domination, Separated Clusters, CD-Coloring: Algorithms and Hardness
by: Antony, Dhanyamol, et al.
Published: (2023)

Parameterized Complexity of s-Club Cluster Edge Deletion: When Is the Diameter Bound Necessary?
by: Gaikwad, Ajinkya
Published: (2025)

Solving the List Coloring Problem through a Branch-and-Price algorithm
by: Lucci, Mauro, et al.
Published: (2023)

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

Edge-Colored Clustering in Hypergraphs: Beyond Minimizing Unsatisfied Edges
by: Crane, Alex, et al.
Published: (2025)

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