On making directed graphs transitive

DOI10.1016/j.jcss.2011.07.001zbMath1280.68104OpenAlexW1968950817MaRDI QIDQ414917

Christian Komusiewicz, Johannes Uhlmann, Mathias Weller, Rolf Niedermeier

Publication date: 11 May 2012

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.jcss.2011.07.001

zbMATH Keywords

NP-hardnessfixed-parameter tractabilitygraph modification problemhierarchical structure detectionkernelization and data reduction

Mathematics Subject Classification ID

Applications of graph theory (05C90) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph algorithms (graph-theoretic aspects) (05C85) Directed graphs (digraphs), tournaments (05C20)

Related Items

Quantifying hierarchical conflicts in homology statements ⋮ Cluster Editing ⋮ A parameterized algorithmics framework for degree sequence completion problems in directed graphs ⋮ Cluster editing with locally bounded modifications ⋮ On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments

Cites Work

• Unnamed Item
• Unnamed Item
• A \(2k\) kernel for the cluster editing problem
• Exact algorithms for cluster editing: Evaluation and experiments
• Graph-modeled data clustering: Exact algorithms for clique generation
• Fixed-parameter algorithms for cluster vertex deletion
• A more effective linear kernelization for cluster editing
• NP-hard problems in hierarchical-tree clustering
• The directed subgraph homeomorphism problem
• Which problems have strongly exponential complexity?
• A general method to speed up fixed-parameter-tractable algorithms
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Even faster parameterized cluster deletion and cluster editing
• Applying modular decomposition to parameterized cluster editing problems
• Parametrized complexity theory.
• Efficient determination of the transitive closure of a directed graph
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Alternative Parameterizations for Cluster Editing
• A Golden Ratio Parameterized Algorithm for Cluster Editing
• Kernelization: New Upper and Lower Bound Techniques
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• The complexity of satisfiability problems
• Efficient Parameterized Preprocessing for Cluster Editing
• Digraphs