The multicolored graph realization problem

DOI10.1016/J.DAM.2022.06.031MaRDI QIDQ6558680zbMATH OpenFDO

Authors J. Díaz, Öznur Yaşar Diner, Maria Serna, Oriol Serra

Publication date 20 June 2024

Published in Discrete Applied Mathematics (Search for Journal in Brave)

zbMATH Keywords

parameterized complexityconvex bipartite graphsgeneralized combinatorial problemsmulticolored realization problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27)

Recommendations

• Clustering on \(k\)-edge-colored graphs
• Clustering on k-Edge-Colored Graphs
• On the complexity of solving or approximating convex recoloring problems
• Hardness and inapproximability of convex recoloring problems
• Maximum colorful cliques in vertex-colored graphs

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• scientific article; zbMATH DE number 2064416 (Why is no real title available?)
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• A retraction problem in graph theory
• A two-level solution approach for solving the generalized minimum spanning tree problem
• Algorithms for Minimum Coloring, Maximum Clique, Minimum Covering by Cliques, and Maximum Independent Set of a Chordal Graph
• An efficient transformation of the generalized vehicle routing problem
• Bipartite permutation graphs
• Finding maximum edge bicliques in convex bipartite graphs
• Fixed-Parameter Tractability and Completeness I: Basic Results
• Fixed-parameter tractability and completeness II: On completeness for W[1]
• Generalized network design problems.
• Generalized network design problems. Modeling and optimization.
• Generalized spanning trees
• Graph theory
• Hardness, approximability, and fixed-parameter tractability of the clustered shortest-path tree problem
• On list \(k\)-coloring convex bipartite graphs
• On list coloring and list homomorphism of permutation and interval graphs
• On some applications of the selective graph coloring problem
• On the complexity of the selective graph coloring problem in some special classes of graphs
• On the generalized minimum spanning tree problem
• On the parameterized complexity of multiple-interval graph problems
• On the parameterized complexity of the fixed alphabet shortest common supersequence and longest common subsequence problems
• Parameterized algorithms
• Parametrized complexity theory.
• The complexity of satisfiability problems
• The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances
• The symmetric generalized traveling salesman polytope

This page was built for publication: The multicolored graph realization problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6558680)