Attributes | Values |
---|
rdf:type
| |
rdfs:seeAlso
| |
Description
| - An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2, 1)-span of a graph is the minimum possible span of its L(2, 1)-labelings. We show how to compute the L(2, 1)-span of a connected graph in time O*(2.6488(n)). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O*(2.5944(n)) for claw-free graphs, and in time O*(2(n-r)(2 + n/r)(r)) for graphs having a dominating set of size r.
- An L(2, 1)-labeling of a graph is a mapping from its vertex set into nonnegative integers such that the labels assigned to adjacent vertices differ by at least 2, and labels assigned to vertices of distance 2 are different. The span of such a labeling is the maximum label used, and the L(2, 1)-span of a graph is the minimum possible span of its L(2, 1)-labelings. We show how to compute the L(2, 1)-span of a connected graph in time O*(2.6488(n)). Previously published exact exponential time algorithms were gradually improving the base of the exponential function from 4 to the so far best known 3, with 3 itself seemingly having been the Holy Grail for quite a while. As concerns special graph classes, we are able to solve the problem in time O*(2.5944(n)) for claw-free graphs, and in time O*(2(n-r)(2 + n/r)(r)) for graphs having a dominating set of size r. (en)
|
Title
| - Fast exact algorithm for L(2,1)-labeling of graphs
- Fast exact algorithm for L(2,1)-labeling of graphs (en)
|
skos:prefLabel
| - Fast exact algorithm for L(2,1)-labeling of graphs
- Fast exact algorithm for L(2,1)-labeling of graphs (en)
|
skos:notation
| - RIV/00216208:11320/13:10191010!RIV14-GA0-11320___
|
http://linked.open...avai/riv/aktivita
| |
http://linked.open...avai/riv/aktivity
| |
http://linked.open...iv/cisloPeriodika
| |
http://linked.open...vai/riv/dodaniDat
| |
http://linked.open...aciTvurceVysledku
| |
http://linked.open.../riv/druhVysledku
| |
http://linked.open...iv/duvernostUdaju
| |
http://linked.open...titaPredkladatele
| |
http://linked.open...dnocenehoVysledku
| |
http://linked.open...ai/riv/idVysledku
| - RIV/00216208:11320/13:10191010
|
http://linked.open...riv/jazykVysledku
| |
http://linked.open.../riv/klicovaSlova
| - Exponential-time algorithm; 1)-labeling; L(2; Graphs (en)
|
http://linked.open.../riv/klicoveSlovo
| |
http://linked.open...odStatuVydavatele
| |
http://linked.open...ontrolniKodProRIV
| |
http://linked.open...i/riv/nazevZdroje
| - Theoretical Computer Science
|
http://linked.open...in/vavai/riv/obor
| |
http://linked.open...ichTvurcuVysledku
| |
http://linked.open...cetTvurcuVysledku
| |
http://linked.open...vavai/riv/projekt
| |
http://linked.open...UplatneniVysledku
| |
http://linked.open...v/svazekPeriodika
| |
http://linked.open...iv/tvurceVysledku
| - Kratochvíl, Jan
- Liedloff, Mathieu
- Junosza-Szaniawski, Konstanty
- Rossmanith, Peter
- Rzazewski, Pawel
|
http://linked.open...ain/vavai/riv/wos
| |
issn
| |
number of pages
| |
http://bibframe.org/vocab/doi
| - 10.1016/j.tcs.2012.06.037
|
http://localhost/t...ganizacniJednotka
| |