A linear time algorithm to compute square of interval graphs and their colouring

DOI10.1016/J.AKCEJ.2016.02.007MaRDI QIDQ322053zbMATH OpenOpenAlexFDO

Authors Satyabrata Paul, Madhumangal Pal, Anita Pal

Publication date 14 October 2016

Published in AKCE International Journal of Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International

Full work available at URL https://doi.org/10.1016/j.akcej.2016.02.007

zbMATH Keywords

\(L(1, 1)\)-labellingcliqueinterval graphsquare of graph

Mathematics Subject Classification ID

Graph labelling (graceful graphs, bandwidth, etc.) (05C78)

Recommendations

• L(2,1)-labeling of interval graphs
• \(L(3, 2, 1)\)- and \(L(4, 3, 2, 1)\)-labeling problems on interval graphs
• An efficient algorithm to solve \(L(0,1)\)-labelling problem on interval graphs
• A characterization of line graphs that are squares of graphs
• Computing the clique-separator graph for an interval graph in linear time

Cites work

• L(2,1)-labeling of interval graphs
• \(T\)-colorings of graphs: recent results and open problems
• A sequential algorithm for finding a maximum weightK-independent set on interval graphs
• Algorithmic graph theory and perfect graphs
• An efficient algorithm to solve \(L(0,1)\)-labelling problem on interval graphs
• An optimal greedy heuristic to color interval graphs
• An optimal parallel algorithm for computing cut vertices and blocks on interval graphs
• An optimal parallel algorithm for solving all-pairs shortest paths problem on circular-arc graphs
• An optimal parallel algorithm to construct a tree 3-spanner on interval graphs
• scientific article; zbMATH DE number 4045800 (Why is no real title available?)
• scientific article; zbMATH DE number 192896 (Why is no real title available?)
• scientific article; zbMATH DE number 1445362 (Why is no real title available?)
• Labelling Graphs with a Condition at Distance 2
• On powers of chordal graphs and their colorings
• Selection of programme slots of television channels for giving advertisement: a graph theoretic approach
• The conditional covering problem on unweighted interval graphs with nonuniform coverage radius

Cited in

(2)

• \(L(3, 2, 1)\)- and \(L(4, 3, 2, 1)\)-labeling problems on interval graphs
• Total domination, separated-cluster, CD-coloring: algorithms and hardness

This page was built for publication: A linear time algorithm to compute square of interval graphs and their colouring

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q322053)