Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
From MaRDI portal
Publication:548676
DOI10.1007/s10288-010-0150-8zbMath1219.05067OpenAlexW2008738806MaRDI QIDQ548676
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
Combinatorial optimization (90C27) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20) Perfect graphs (05C17)
Related Items (3)
Directed acyclic graphs with the unique dipath property ⋮ On the kernel and related problems in interval digraphs ⋮ Perfect graphs with polynomially computable kernels
Cites Work
- Primal-dual approximation algorithms for integral flow and multicut in trees
- Minimal multicut and maximal integer multiflow: a survey
- Decomposition by clique separators
- Intersection graphs of paths in a tree
- Perfect graphs are kernel solvable
- Geometric algorithms and combinatorial optimization
- On the complexity of the parity argument and other inefficient proofs of existence
- Fractional kernels in digraphs
- Combinatorial optimization in geometry
- A greedy algorithm for multicut and integral multiflow in rooted trees
- Optimal wavelength routing on directed fiber trees
- Traffic grooming on the path
- Normal hypergraphs and the perfect graph conjecture
- Solutions of irreflexive relations
- Stable marriage assignment for unequal sets
- College Admissions and the Stability of Marriage
- Unnamed Item
This page was built for publication: Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree