The permutation-path coloring problem on trees.

DOI10.1016/S0304-3975(02)00635-7MaRDI QIDQ1401295zbMATH OpenOpenAlexFDO

Authors Sylvie Corteel, Mario Valencia-Pabon, Alain Denise, Danièle Gardy, D. Barth

Publication date 17 August 2003

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

Full work available at URL https://doi.org/10.1016/s0304-3975(02)00635-7

zbMATH Keywords

NP-completenessAverage-case complexityPath coloringRouting permutationTree networks

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1512699
• Coloring permutation graphs in parallel
• The complexity of path coloring and call scheduling
• scientific article; zbMATH DE number 1436135
• Randomized path coloring on binary trees.

Cites work

• scientific article; zbMATH DE number 3859178 (Why is no real title available?)
• scientific article; zbMATH DE number 3943829 (Why is no real title available?)
• scientific article; zbMATH DE number 3637904 (Why is no real title available?)
• scientific article; zbMATH DE number 1303573 (Why is no real title available?)
• scientific article; zbMATH DE number 910915 (Why is no real title available?)
• A note on optical routing on trees
• Coloring a Family of Circular Arcs
• Colouring paths in directed symmetric trees with applications to WDM routing
• Combinatorial aspects of continued fractions
• Dynamic analysis of some relational databases parameters
• Efficient algorithms for interval graphs and circular-arc graphs
• Efficient routing in all-optical networks
• Eulerian graphs and related topics. Part 1, Volume 2
• On the capacity of disjointly shared networks
• Optimal wavelength routing on directed fiber trees
• Permutations depending on the exceedance type and the number of inversions and combinatorial interpretation of a continued fraction of Heine
• Permutations selon leurs pics, creux, doubles montees et double descentes, nombres d'Euler et nombres de Genocchi
• Random walks, Gaussian processes and list structures
• Routing a permutation in the hypercube by two sets of edge disjoint paths
• The Complexity of Coloring Circular Arcs and Chords
• The maximum concurrent flow problem
• The maximum of a Gaussian process whose mean path has a maximum, with an application to the strength of bundles of fibres
• The maximum of a random walk whose mean path has a maximum

Cited in

(3)

• Model-hierarchical column generation and heuristic for the routing and wavelength assignment problem
• scientific article; zbMATH DE number 1512699 (Why is no real title available?)
• Routing permutations and involutions on optical ring networks: Complexity results and solution to an open problem

This page was built for publication: The permutation-path coloring problem on trees.

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