Online problems, pathwidth, and persistence

DOI10.1007/978-3-540-28639-4_2MaRDI QIDQ5311514zbMATH OpenOpenAlexFDO

Authors Catherine McCartin, Rodney G. Downey

Publication date 23 August 2005

Published in Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/b100584

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Graph theory (including graph drawing) in computer science (68R10) General topics in the theory of algorithms (68W01)

Recommendations

• Online promise problems with online width metrics
• The online graph bandwidth problem
• Advice complexity of online coloring for paths
• Online coloring known graphs
• Tight bounds for online coloring of basic graph classes

Cited in

(5)

• Foundations of online structure theory. II: The operator approach
• Online, computable and punctual structure theory
• Online promise problems with online width metrics
• Escaping offline searchers and isoperimetric theorems
• Parameterized approximation of dominating set problems

This page was built for publication: Online problems, pathwidth, and persistence

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