On making directed graphs transitive
DOI10.1016/J.JCSS.2011.07.001zbMATH Open1280.68104OpenAlexW1968950817MaRDI QIDQ414917FDOQ414917
Authors: Mathias Weller, Christian Komusiewicz, Rolf Niedermeier, Johannes Uhlmann 
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
Recommendations
fixed-parameter tractabilityNP-hardnessgraph modification problemhierarchical structure detectionkernelization and data reduction
Applications of graph theory (05C90) Directed graphs (digraphs), tournaments (05C20) Graph algorithms (graph-theoretic aspects) (05C85) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Cites Work
- Automated generation of search tree algorithms for hard graphs modification problems
- Applying modular decomposition to parameterized cluster editing problems
- A \(2k\) kernel for the cluster editing problem
- Fixed-parameter algorithms for cluster vertex deletion
- The directed subgraph homeomorphism problem
- Which problems have strongly exponential complexity?
- 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
- The complexity of satisfiability problems
- Digraphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
- Cluster graph modification problems
- Kernelization: new upper and lower bound techniques
- A more effective linear kernelization for cluster editing
- A general method to speed up fixed-parameter-tractable algorithms
- Even faster parameterized cluster deletion and cluster editing
- NP-hard problems in hierarchical-tree clustering
- Alternative parameterizations for cluster editing
- A golden ratio parameterized algorithm for cluster editing
- Exact algorithms for cluster editing: Evaluation and experiments
- Efficient Parameterized Preprocessing for Cluster Editing
- Graph-modeled data clustering: Exact algorithms for clique generation
Cited In (9)
- Title not available (Why is that?)
- On Making Directed Graphs Transitive
- Cluster editing with locally bounded modifications
- A parameterized algorithmics framework for degree sequence completion problems in directed graphs
- On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
- Title not available (Why is that?)
- Cluster editing
- Quantifying hierarchical conflicts in homology statements
- Inferring (biological) signal transduction networks via transitive reductions of directed graphs
This page was built for publication: On making directed graphs transitive
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q414917)
