NDLI: An algorithm for Hierarchical Chinese postman problem using minimum spanning tree approach based on Kruskal's algorithm

Content Provider	IEEE Xplore Digital Library
Author	Sayata, U.B. Desai, N.P.
Copyright Year	2015
Description	Author affiliation: Dept. of Inf. Technol., Dharmsinh Desai Univ., Nadiad-Gujarat, India (Sayata, U.B.; Desai, N.P.)
Abstract	The Hierarchical Chinese postman problem is a special type of Chinese postman problem. The aim is to find a shortest tour that traverses each edge of a given graph at least once. The constraint is that the arcs are partitioned into classes and a precedence relation orders the classes according to priority. Different forms of the HCPP are applied in real life applications such as snow plowing, winter gritting and street sweeping. The problem is solvable in polynomial time if the ordering relation is linear and each class is connected. Dror et al. (1987) presented an algorithm which provides time complexity of O $(kn^{5}).$ CPP which is lower bound for HCPP. We give alternate approach by using Kruskal's method to reduce number of edges in graph which is having time complexity of O $(k^{2}n^{2}),$ where k is number of layers in graph and n is number of nodes in graph. It is found that the suggested kruskal-based HCPP-solution gives average 21.64% improvement compare to simple HCPP and we get average 13.35% improvement over CPP when number of hierarchy is less than 3 and numbers of edges in graph are less than 10.
Starting Page	222
Ending Page	227
File Size	1127787
Page Count	6
File Format	PDF
e-ISBN	9781479980475
DOI	10.1109/IADCC.2015.7154702
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2015-06-12
Publisher Place	India
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Chinese postman problem (CPP) Hierarchical Chinese Postman Problem (HCPP) NP-hard problem Conferences Polynomials Partitioning algorithms Time complexity Information technology NP-Hard Problem Travelling Salesman Problem
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem

Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

An effective ant-based algorithm for the degree-constrained minimum spanning tree problem

A parallel algorithm for the degree-constrained minimum spanning tree problem using nearest-neighbor chains

Branch-and-bound algorithm for the time dependent Chinese Postman Problem

Clustered Trees with Minimum Inter-cluster Distance

Postman problems, priorities and the concept of servicing (2002).

Kruskal's minimum spanning tree approach to brain fiber tractography computation

Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

An algorithm for Hierarchical Chinese postman problem using minimum spanning tree approach based on Kruskal's algorithm

Similar Documents

A Preliminary Study on Minimum Spanning Tree Algorithm Approach for Travelling Salesman Problem

Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

An effective ant-based algorithm for the degree-constrained minimum spanning tree problem

A parallel algorithm for the degree-constrained minimum spanning tree problem using nearest-neighbor chains

Branch-and-bound algorithm for the time dependent Chinese Postman Problem

Clustered Trees with Minimum Inter-cluster Distance

Postman problems, priorities and the concept of servicing (2002).

Kruskal's minimum spanning tree approach to brain fiber tractography computation

Implementation of Heuristics for Solving Travelling Salesman Problem Using Nearest Neighbour and Minimum Spanning Tree Algorithms

An algorithm for Hierarchical Chinese postman problem using minimum spanning tree approach based on Kruskal's algorithm