• Login
    JavaScript is disabled for your browser. Some features of this site may not work without it.

    Browse

    All of DSpaceCommunities & CollectionsBy Issue DateAuthorsTitlesSubjectsThis CollectionBy Issue DateAuthorsTitlesSubjects

    My Account

    LoginRegister

    Statistics

    View Usage StatisticsView Google Analytics Statistics

    The Study of Vertex Coloring Algorithms Using Heuristic Approaches

    Thumbnail
    View/Open
    201611016 (1.110Mb)
    Date
    2018
    Author
    Lodha, Pratik
    Metadata
    Show full item record
    Abstract
    Graph vertex coloring is one of the most studied NP-complete optimization problem (READ, 1972) [2]. The problem is that; given a graph G, determine the number of colors required to color G, so that no two adjacent vertices share the same color. And the minimum number of colors required to color graph is known as Chromatic Number and is denoted by ?(G). By using existing properties of eccentricity, BFS, DFS (West, 2000) [3] and graph components we have proposed three new heuristic algorithms to obtain approximated chromatic number of a given graph G. And these approaches are as follows: 1. Eccentricity based coloring 2. DFS based coloring, and 3. Maximum degree based coloring.
    URI
    http://drsr.daiict.ac.in//handle/123456789/731
    Collections
    • M Tech Dissertations [820]

    Related items

    Showing items related by title, author, creator and subject.

    • Downsampling of signals on graphs: an algebraic perspective 

      Vaishnav, Nileshkumar (Dhirubhai Ambani Institute of Information and Communication Technology, 2018)
      Real-world data such as weather data, seismic activity data, sensor networks data and social network data can be represented and processed conveniently using a mathematical structure called Graph. Graphs are a collection ...
    • Acyclic edge coloring of complete r-partite graphs 

      Teja, V. Krishna (Dhirubhai Ambani Institute of Information and Communication Technology, 2011)
      An acyclic edge coloring of a graph G is a proper edge coloring of G which has no dichromatic cycle. The minimum number of colors required to acyclically edge color graph G is called its acyclic chromatic index, denoted ...
    • Study on shock graphs: graph representation of objects 

      Desai, Abhi Hitesh (Dhirubhai Ambani Institute of Information and Communication Technology, 2013)
      A shock graph is an abstraction of a two-dimensional shape of an object. It represents the shape as a graph, using its boundary information. In this thesis, we study the shock graph representation of two-dimensional shapes. ...

    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV
     

     


    Resource Centre copyright © 2006-2017 
    Contact Us | Send Feedback
    Theme by 
    Atmire NV