Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree

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

zbMATH Keywords

intersection graphkernelmulticutdirected treeDE graphminimum clique cover

Mathematics Subject Classification ID

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