Skip to content

How to get a degree-anonymous graph using minimum number of edge rotations

Research output: Chapter in Book/Report/Conference proceedingConference contribution

A graph is k-degree-anonymous if for each vertex there are at least (k-1) other vertices of the same degree in the graph. The Min Anonymous-Edge-Rotation problem asks for a given graph G and a positive integer k to find a minimum number of edge rotations that transform G into a k-degree-anonymous graph. In this paper, we establish sufficient conditions for an input graph and k ensuring that a solution for the problem exists. We also prove that the Min Anonymous-Edge-Rotation problem is NP-hard even for k=n/3, where n is the order of a graph. On the positive side, we argue that under some constraints on the number of edges in a graph and k, Min Anonymous-Edge-Rotation is polynomial-time 2-approximable. Moreover, we show that the problem is solvable in polynomial time for any graph when k=n and for trees when k=θ(n).
Original languageEnglish
Title of host publicationCombinatorial Optimization and Applications
Subtitle of host publication14th International Conference, COCOA 2020, Dallas, TX, USA, December 11–13, 2020, Proceedings
EditorsWeili Wu, Zhongnan Zhang
PublisherSpringer
Pages242-256
Number of pages12
ISBN (Electronic)978-3-030-64843-5
ISBN (Print)978-3-030-64842-8
DOIs
Publication statusPublished - 4 Dec 2020
Event14th Annual International Conference on Combinatorial Optimization and Applications - Dallas, United States
Duration: 11 Dec 202013 Dec 2020
Conference number: 14
https://theory.utdallas.edu/COCOA2020/index.html

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume12577
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Conference

Conference14th Annual International Conference on Combinatorial Optimization and Applications
Abbreviated titleCOCOA
CountryUnited States
CityDallas
Period11/12/2013/12/20
Internet address

Documents

  • Cocoa2020

    Rights statement: This is a post-peer-review, pre-copyedit version of an article published in Lecture Notes in Computer Science. The final authenticated version is available online at: http://dx.doi.org/10.1007/978-3-030-64843-5_17.

    Accepted author manuscript (Post-print), 356 KB, PDF document

    Due to publisher’s copyright restrictions, this document is not freely available to download from this website until: 4/12/21

Related information

Relations Get citation (various referencing formats)

ID: 22856906