Graph orientation with splits
| Autor: | Hesam Nikpey, Eiji Miyano, Hirotaka Ono, Yuichi Asahiro, Jesper Jansson |
|---|---|
| Rok vydání: | 2020 |
| Předmět: |
General Computer Science
Computational complexity theory Maximum flow Maximum flow problem Vertex cover 0102 computer and information sciences 02 engineering and technology New variant 01 natural sciences Graph Theoretical Computer Science Algorithm Computational complexity Combinatorics 010201 computation theory & mathematics 0202 electrical engineering electronic engineering information engineering 020201 artificial intelligence & image processing Graph orientation Partition MathematicsofComputing_DISCRETEMATHEMATICS Mathematics |
| Zdroj: | Theoretical Computer Science. 844:16-25 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2020.07.013 |
| Popis: | The Minimum Maximum Outdegree Problem (MMO) is to assign a direction to every edge in an input undirected, edge-weighted graph so that the maximum weighted outdegree taken over all vertices becomes as small as possible. In this paper, we introduce a new variant of MMO called the p-Split Minimum Maximum Outdegree Problem (p-Split-MMO) in which one is allowed to perform a sequence of p split operations on the vertices before orienting the edges, for some specified non-negative integer p, and study its computational complexity. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect