Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
DOI10.1007/S10288-010-0150-8zbMATH Open1219.05067OpenAlexW2008738806MaRDI QIDQ548676FDOQ548676
Julien Reygner, Olivier Durand de Gevigney, Ayrin Romero, Frédéric Meunier, Christian Popa
Publication date: 30 June 2011
Published in: 4OR (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1007/s10288-010-0150-8
Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Perfect graphs (05C17)
Cites Work
- Title not available (Why is that?)
- Geometric algorithms and combinatorial optimization
- Normal hypergraphs and the perfect graph conjecture
- Decomposition by clique separators
- Intersection graphs of paths in a tree
- Solutions of irreflexive relations
- College Admissions and the Stability of Marriage
- Minimal multicut and maximal integer multiflow: a survey
- Stable marriage assignment for unequal sets
- On the complexity of the parity argument and other inefficient proofs of existence
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Perfect graphs are kernel solvable
- Optimal wavelength routing on directed fiber trees
- Traffic grooming on the path
- Fractional kernels in digraphs
- Combinatorial optimization in geometry
- A greedy algorithm for multicut and integral multiflow in rooted trees
Cited In (3)
This page was built for publication: Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q548676)
