About: Faster Heuristics for Graph Burning

Facets (new session)
Description
Metadata
Settings
- owl:sameAs
- Inference Rule:

About: Faster Heuristics for Graph Burning Goto Sponge NotDistinct Permalink

An Entity of Type : schema:ScholarlyArticle, within Data Space : wasabi.inria.fr associated with source document(s)

Attributes	Values
type	Academic Article research paper schema:ScholarlyArticle
isDefinedBy	Covid-on-the-Web dataset
has title	Faster Heuristics for Graph Burning
Creator	Durga Bhavani, S Gautam, Rahul Kare, Anjeneya
topic	covid:7dc49b61e272577e6672631c7794d622505d9681#this
Source	ArXiv
abstract	Graph burning is a process of information spreading through the network by an agent in discrete steps. The problem is to find an optimal sequence of nodes which have to be given information so that the network is covered in least number of steps. Graph burning problem is NP-Hard for which two approximation algorithms and a few heuristics have been proposed in the literature. In this work, we propose three heuristics, namely, Backbone Based Greedy Heuristic (BBGH), Improved Cutting Corners Heuristic (ICCH) and Component Based Recursive Heuristic (CBRH). These are mainly based on Eigenvector centrality measure. BBGH finds a backbone of the network and picks vertex to be burned greedily from the vertices of the backbone. ICCH is a shortest path based heuristic and picks vertex to burn greedily from best central nodes. The burning number problem on disconnected graphs is harder than on the connected graphs. For example, burning number problem is easy on a path where as it is NP-Hard on disjoint paths. In practice, large networks are generally disconnected and moreover even if the input graph is connected, during the burning process the graph among the unburned vertices may be disconnected. For disconnected graphs, ordering of the components is crucial. Our CBRH works well on disconnected graphs as it prioritizes the components. All the heuristics have been implemented and tested on several bench-mark networks including large networks of size more than $50$K nodes. The experimentation also includes comparison to the approximation algorithms. The advantages of our algorithms are that they are much simpler to implement and also several orders faster than the heuristics proposed in the literature.
has issue date	2020-08-20(xsd:dateTime)
has license	arxiv
sha1sum (hex)	7dc49b61e272577e6672631c7794d622505d9681
resource representing a document's title	Faster Heuristics for Graph Burning
resource representing a document's body	covid:7dc49b61e272577e6672631c7794d622505d9681#body_text
is http://vocab.deri.ie/void#inDataset of	https://covidontheweb.inria.fr:4443/about/id/http/ns.inria.fr/covid19/7dc49b61e272577e6672631c7794d622505d9681
is schema:about of	named entity 'based' named entity 'Graph' named entity 'Heuristic' named entity 'network' named entity 'Eigenvector centrality' named entity 'Graph' named entity 'path' named entity 'agent' named entity 'OPTIMAL' named entity 'EASY' named entity 'INPUT' named entity 'COMPONENTS' named entity 'PROCESS' named entity 'INCLUDING' named entity 'EXAMPLE' named entity 'NUMBER' named entity 'GIVEN' named entity 'BURN' named entity 'SHORTEST' named entity 'FASTER' named entity 'VERTEX' named entity 'AGENT' named entity 'BEST' named entity 'GENERALLY' named entity 'IMPLEMENTED' named entity 'GRAPH' named entity 'SIZE' named entity 'SEQUENCE' named entity 'BURNED' named entity 'INFORMATION' named entity 'ORDERING' named entity 'problem' named entity 'disconnected' named entity 'networks' named entity 'Corners' named entity 'number' named entity 'Our' named entity 'networks' named entity 'graphs' named entity 'For' named entity 'covered' named entity 'backbone' named entity 'network' named entity 'graphs' named entity 'heuristics' named entity 'heuristic' named entity 'vertices' named entity 'Greedy Heuristic' named entity 'graph' named entity 'Graph' named entity 'vertex' named entity 'approximation algorithms' named entity 'CBRH' named entity 'Eigenvector Centrality' named entity 'approximation algorithm' named entity 'algorithm' named entity 'heuristic' named entity 'synthetic data' named entity 'approximation algorithm' named entity 'polynomial time' named entity 'Greedy Heuristic' named entity 'heuristics' named entity 'heuristics' named entity 'heuristics' named entity 'CBRH' named entity 'algorithm' named entity 'Greedy Algorithm' named entity 'heuristics' named entity 'heuristics' named entity 'CBRH' named entity 'heuristics' named entity 'heuristics' named entity 'Approximation algorithms' named entity 'NP-Complete' named entity 'firefighter' named entity 'greedy heuristic' named entity 'CBRH' named entity 'approximation algorithm' named entity 'Šimon' named entity 'greedy algorithms' named entity 'eigenvector centrality' named entity 'algorithm' named entity 'heuristics'

Faceted Search & Find service v1.13.91 as of Mar 24 2020

Alternative Linked Data Documents: Sponger | ODE Content Formats:

RDF

ODATA

Microdata

About

OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software