On-line ranking of split graphs

zbMATH Open1282.68197MaRDI QIDQ5747397FDOQ5747397

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

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

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)

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)