Online promise problems with online width metrics

DOI10.1016/j.jcss.2006.08.002zbMath1178.68375OpenAlexW2020138610MaRDI QIDQ859981

Catherine McCartin, Rodney G. Downey

Publication date: 22 January 2007

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2006.08.002

zbMATH Keywords

persistencetreewidthonline algorithmspathwidthparameterized complexityonline coloring

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Graph theory (including graph drawing) in computer science (68R10)

Related Items (3)

Tight bounds for online coloring of basic graph classes ⋮ Tight Bounds for Online Coloring of Basic Graph Classes ⋮ Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• An on-line graph coloring algorithm with sublinear performance ratio
• Graph minors. X: Obstructions to tree-decomposition
• A partial k-arboretum of graphs with bounded treewidth
• Coloring inductive graphs on-line
• Coloring interval graphs with First-Fit
• Beyond NP-completeness for problems of bounded width (extended abstract)
• Algorithms finding tree-decompositions of graphs
• Graph minors. II. Algorithmic aspects of tree-width
• Complexity of Finding Embeddings in a k-Tree
• On-line and first fit colorings of graphs
• The Linearity of First-Fit Coloring of Interval Graphs
• On some packing problem related to dynamic storage allocation
• Domino Treewidth
• Efficient Parallel Algorithms for Graphs of Bounded Tree-Width
• The Linkage of a Graph
• Efficient and Constructive Algorithms for the Pathwidth and Treewidth of Graphs
• AN IMPROVED ALGORITHM FOR FINDING TREE DECOMPOSITIONS OF SMALL WIDTH
• A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth

This page was built for publication: Online promise problems with online width metrics