Towards transitive-free digraphs

DOI10.1016/J.TCS.2025.115270MaRDI QIDQ6985812zbMATH OpenFDO

Authors Ankit Abhinav, Satyabrata Jana, Abhishek Sahu

Publication date 12 May 2025

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

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115270

zbMATH Keywords

bounded independence numberDAGFPTkernelizationlocal tournamentsNP-hardnesstournamentstransitive-free digraphs

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Parameterized complexity, tractability and kernelization (68Q27) Graph theory (including graph drawing) in computer science (68R10)

Cites work

• \(st\)-orientations with few transitive edges
• A kernelization algorithm for \(d\)-hitting set
• Face covers and the genus problem for apex graphs
• Fixed-parameter tractability of multicut in directed acyclic graphs
• Forbidding just one intersection
• scientific article; zbMATH DE number 3165195 (Why is no real title available?)
• scientific article; zbMATH DE number 5485529 (Why is no real title available?)
• scientific article; zbMATH DE number 686998 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• scientific article; zbMATH DE number 7650395 (Why is no real title available?)
• Locally semicomplete digraphs: A generalization of tournaments
• On the complexity of singly connected vertex deletion
• On the perspectives opened by right angle crossing drawings
• Parametrized complexity theory.
• Three-dimensional orthogonal graph drawing algorithms

This page was built for publication: Towards transitive-free digraphs

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