Maximum cuts in edge-colored graphs
DOI10.1016/j.dam.2019.02.038zbMath1440.05085arXiv1805.00858OpenAlexW2964140139MaRDI QIDQ5918845
Sulamita Klein, Ignasi Sau, Rubens Sucupira, Uéverton S. Souza, Luérbio Faria
Publication date: 29 May 2020
Published in: Discrete Applied Mathematics, Electronic Notes in Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1805.00858
maximum cutplanar graphparameterized complexitypolynomial kerneledge cutmax cutedge cutscolored cutcolored cuts
Analysis of algorithms and problem complexity (68Q25) Extremal problems in graph theory (05C35) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (2)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- The label cut problem with respect to path length and label frequency
- Approximation and hardness results for label cut and related problems
- The labeled perfect matching in bipartite graphs
- Some simplified NP-complete graph problems
- A partial k-arboretum of graphs with bounded treewidth
- Simpler and better approximation algorithms for the unweighted minimum label \(s\)-\(t\) cut problem
- The parameterized complexity of some minimum label problems
- On some extremal problems in graph theory
- Complexity insights of the minimum duplication problem
- Parametrized complexity theory.
- Approximating Minimum Label s-t Cut via Linear Programming
- Finding a Maximum Cut of a Planar Graph in Polynomial Time
- Spanning trees with many or few colors in edge-colored graphs
- The complexity of satisfiability problems
- Efficient Algorithms for the Label Cut Problems
- Parameterized Algorithms
- Maximum cuts in edge-colored graphs
This page was built for publication: Maximum cuts in edge-colored graphs
