Antibandwidth problem for itchy caterpillars

Md Sazzadur Rahaman; Tousif Ahmed Eshan; Sad Al Abdullah; Md Saidur Rahman

doi:10.1109/ICIEV.2014.6850837

Antibandwidth problem for itchy caterpillars

Md Sazzadur Rahaman, Tousif Ahmed Eshan, Sad Al Abdullah, Md Saidur Rahman

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

3 Scopus citations

Abstract

The antibandwidth problem is to label the vertices of a graph of n vertices by 1, 2, 3,..., n bijectively, such that the minimum difference of labels of adjacent vertices is maximized. The antibandwidth problem is known as NP-hard for general graphs. In this paper, we give an antibandwidth labeling scheme for a special class of trees called itchy caterpillar and study the lower bound of antibandwidth problem for the same class of graphs. We also give exact results for some of its subclasses. The result for itchy caterpillars with hair length 1, is the first nontrivial exact result of antibandwidth problem for any class of graphs.

Original language	English (US)
Title of host publication	2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014
Publisher	IEEE Computer Society
ISBN (Print)	9781479951796
DOIs	https://doi.org/10.1109/ICIEV.2014.6850837
State	Published - 2014
Externally published	Yes
Event	2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014 - Dhaka, Bangladesh Duration: May 23 2014 → May 24 2014

Publication series

Name	2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014

Conference

Conference	2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014
Country/Territory	Bangladesh
City	Dhaka
Period	5/23/14 → 5/24/14

ASJC Scopus subject areas

Computer Vision and Pattern Recognition
Electrical and Electronic Engineering

Access to Document

10.1109/ICIEV.2014.6850837

Cite this

Antibandwidth problem for itchy caterpillars. / Rahaman, Md Sazzadur; Eshan, Tousif Ahmed; Al Abdullah, Sad et al.
2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014. IEEE Computer Society, 2014. 6850837 (2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Rahaman, MS, Eshan, TA, Al Abdullah, S & Rahman, MS 2014, Antibandwidth problem for itchy caterpillars. in 2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014., 6850837, 2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014, IEEE Computer Society, 2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014, Dhaka, Bangladesh, 5/23/14. https://doi.org/10.1109/ICIEV.2014.6850837

@inproceedings{171933ec66a44501a4c4fa85c3ae942b,

title = "Antibandwidth problem for itchy caterpillars",

abstract = "The antibandwidth problem is to label the vertices of a graph of n vertices by 1, 2, 3,..., n bijectively, such that the minimum difference of labels of adjacent vertices is maximized. The antibandwidth problem is known as NP-hard for general graphs. In this paper, we give an antibandwidth labeling scheme for a special class of trees called itchy caterpillar and study the lower bound of antibandwidth problem for the same class of graphs. We also give exact results for some of its subclasses. The result for itchy caterpillars with hair length 1, is the first nontrivial exact result of antibandwidth problem for any class of graphs.",

author = "Rahaman, {Md Sazzadur} and Eshan, {Tousif Ahmed} and {Al Abdullah}, Sad and Rahman, {Md Saidur}",

year = "2014",

doi = "10.1109/ICIEV.2014.6850837",

language = "English (US)",

isbn = "9781479951796",

series = "2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014",

publisher = "IEEE Computer Society",

booktitle = "2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014",

note = "2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014 ; Conference date: 23-05-2014 Through 24-05-2014",

}

TY - GEN

T1 - Antibandwidth problem for itchy caterpillars

AU - Rahaman, Md Sazzadur

AU - Eshan, Tousif Ahmed

AU - Al Abdullah, Sad

AU - Rahman, Md Saidur

PY - 2014

Y1 - 2014

N2 - The antibandwidth problem is to label the vertices of a graph of n vertices by 1, 2, 3,..., n bijectively, such that the minimum difference of labels of adjacent vertices is maximized. The antibandwidth problem is known as NP-hard for general graphs. In this paper, we give an antibandwidth labeling scheme for a special class of trees called itchy caterpillar and study the lower bound of antibandwidth problem for the same class of graphs. We also give exact results for some of its subclasses. The result for itchy caterpillars with hair length 1, is the first nontrivial exact result of antibandwidth problem for any class of graphs.

AB - The antibandwidth problem is to label the vertices of a graph of n vertices by 1, 2, 3,..., n bijectively, such that the minimum difference of labels of adjacent vertices is maximized. The antibandwidth problem is known as NP-hard for general graphs. In this paper, we give an antibandwidth labeling scheme for a special class of trees called itchy caterpillar and study the lower bound of antibandwidth problem for the same class of graphs. We also give exact results for some of its subclasses. The result for itchy caterpillars with hair length 1, is the first nontrivial exact result of antibandwidth problem for any class of graphs.

UR - http://www.scopus.com/inward/record.url?scp=84904968326&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84904968326&partnerID=8YFLogxK

U2 - 10.1109/ICIEV.2014.6850837

DO - 10.1109/ICIEV.2014.6850837

M3 - Conference contribution

AN - SCOPUS:84904968326

SN - 9781479951796

T3 - 2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014

BT - 2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014

PB - IEEE Computer Society

T2 - 2014 International Conference on Informatics, Electronics and Vision, ICIEV 2014

Y2 - 23 May 2014 through 24 May 2014

ER -

Antibandwidth problem for itchy caterpillars

Abstract

Publication series

Conference

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this