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

greedy algorithmgraph coloringsplit graphadvice complexityon-line algorithmgraph rankingsemi on-line algorithm

Mathematics Subject Classification ID

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

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)

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

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)