Parameterized maximum path coloring

DOI10.1016/J.TCS.2013.01.012MaRDI QIDQ392021zbMATH OpenOpenAlexFDO

Authors Michael Lampis

Publication date 13 January 2014

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2013.01.012

zbMATH Keywords

parameterized complexityEPT graphspath coloring

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Recommendations

• Parameterized maximum path coloring
• Fractional path coloring in bounded degree trees with applications
• Approximation Algorithms for Path Coloring in Trees
• The complexity of path coloring and call scheduling
• scientific article; zbMATH DE number 1839474

Cites work

• scientific article; zbMATH DE number 1303779 (Why is no real title available?)
• scientific article; zbMATH DE number 637355 (Why is no real title available?)
• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A note on optical routing on trees
• Algorithmic meta-theorems for restrictions of treewidth
• Call control with \(k\) rejections
• Color-coding
• Edge and vertex intersection of paths in a tree
• Linear FPT reductions and computational lower bounds
• On the complexity of \(k\)-SAT
• Optimal wavelength routing on directed fiber trees
• Parametrized complexity theory.
• Primal-dual approximation algorithms for integral flow and multicut in trees
• The Complexity of Coloring Circular Arcs and Chords
• The complexity of path coloring and call scheduling
• The maximum edge-disjoint paths problem in bidirected trees

Cited in

(6)

• A note on the parameterized complexity of unordered maximum tree orientation
• Fixed-parameter tractability of maximum colored path and beyond
• Saving colors and max coloring: some fixed-parameter tractability results
• Grundy distinguishes treewidth from pathwidth
• Parameterized maximum path coloring
• Grundy Distinguishes Treewidth from Pathwidth

This page was built for publication: Parameterized maximum path coloring

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