On the kernel and related problems in interval digraphs
From MaRDI portal
Publication:6103517
DOI10.1007/s00453-022-01010-1arXiv2107.08278OpenAlexW3185570678MaRDI QIDQ6103517
Dalu Jacob, Pavol Hell, Mathew C. Francis
Publication date: 5 June 2023
Published in: Algorithmica (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/2107.08278
Related Items (1)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- A linear time algorithm to compute a maximum weighted independent set on cocomparability graphs
- Recognition and characterization of chronological interval digraphs
- Interval graphs, adjusted interval digraphs, and reflexive list homomorphisms
- Independent dominating set problem revisited
- Solving coloring, minimum clique cover and kernel problems on arc intersection graphs of directed paths on a tree
- On kernels in perfect graphs
- On kernels and semikernels of digraphs
- Polynomial algorithms for kernels in comparability, permutation and \(P_4\)-free graphs
- Kernels in perfect line-graphs
- On finding a minimum dominating set in a tournament
- A characterization of interval catch digraphs
- Perfect graphs are kernel solvable
- Planar kernel and Grundy with \(d\leq 3\), \(dout\leq 2\), \(din\leq 2\) are NP- complete
- Optimization, approximation, and complexity classes
- Modular decomposition and transitive orientation
- Algorithms for interval catch digraphs
- Recognizing interval digraphs and interval bigraphs in polynomial time
- Domination in tournaments
- On kernels in i-triangulated graphs
- Fixed parameter algorithms for DOMINATING SET and related problems on planar graphs
- Bounded bitolerance digraphs
- Kernels in random graphs
- Perfect graphs with polynomially computable kernels
- Perfect graphs, kernels, and cores of cooperative games
- Dominating sets in \(k\)-majority tournaments.
- Recent problems and results about kernels in directed graphs
- Solutions of irreflexive relations
- A recognition algorithm for adjusted interval digraphs
- Domination on Cocomparability Graphs
- A digraph represented by a family of boxes or spheres
- Incompressibility through Colors and IDs
- A sufficient condition for a digraph to be kernel-perfect
- Interval digraphs: An analogue of interval graphs
- The Complexity of Combinatorial Optimization Problems on d‐Dimensional Boxes
- Extension Theorems for Solutions of Irreflexive Relations
- On weakly ordered systems
- College Admissions and the Stability of Marriage
- Recognizing interval bigraphs by forbidden patterns
This page was built for publication: On the kernel and related problems in interval digraphs
