On-line ranking of split graphs

MaRDI QIDQ5747397zbMATH OpenFDO

Authors Piotr Borowiecki, Dariusz Dereniowski

Publication date 14 February 2014

Full work available at URL https://www.dmtcs.org/dmtcs-ojs/index.php/dmtcs/article/view/1316/0.html

zbMATH Keywords

advice complexitygraph coloringgraph rankinggreedy algorithmon-line algorithmsemi on-line algorithmsplit graph

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Graph labelling (graceful graphs, bandwidth, etc.) (05C78) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Online algorithms; streaming algorithms (68W27)

Recommendations

• On-line rankings of graphs
• On vertex ranking of a starlike graph
• A note on on-line ranking number of graphs
• On-line vertex ranking of trees
• A lower bound for on-line ranking number of a path

Cited in

(4)

• List rankings and on-line list rankings of graphs
• On-line vertex ranking of trees
• On node ranking of complete r-partite graphs
• The complexity of bicriteria tree-depth

This page was built for publication: On-line ranking of split graphs

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