On making directed graphs transitive

DOI10.1016/J.JCSS.2011.07.001MaRDI QIDQ414917zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

fixed-parameter tractabilityNP-hardnessgraph modification problemhierarchical structure detectionkernelization and data reduction

Mathematics Subject Classification ID

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)

Recommendations

• On Making Directed Graphs Transitive
• scientific article; zbMATH DE number 15035
• Speeding up dynamic transitive closure for bounded degree graphs
• scientific article; zbMATH DE number 4156472
• Making Arbitrary Graphs Transitively Orientable: Minimal Comparability Completions

Cites work

• scientific article; zbMATH DE number 1161563 (Why is no real title available?)
• scientific article; zbMATH DE number 2234775 (Why is no real title available?)
• A \(2k\) kernel for the cluster editing problem
• A general method to speed up fixed-parameter-tractable algorithms
• A golden ratio parameterized algorithm for cluster editing
• A more effective linear kernelization for cluster editing
• Alternative parameterizations for cluster editing
• Applying modular decomposition to parameterized cluster editing problems
• Automated generation of search tree algorithms for hard graphs modification problems
• Cluster graph modification problems
• Digraphs
• Efficient Parameterized Preprocessing for Cluster Editing
• Efficient determination of the transitive closure of a directed graph
• Even faster parameterized cluster deletion and cluster editing
• Exact algorithms for cluster editing: Evaluation and experiments
• Exploiting Bounded Signal Flow for Graph Orientation Based on Cause–Effect Pairs
• Finding Two Disjoint Paths Between Two Pairs of Vertices in a Graph
• Fixed-parameter algorithms for cluster vertex deletion
• Graph-modeled data clustering: Exact algorithms for clique generation
• Kernelization: new upper and lower bound techniques
• NP-hard problems in hierarchical-tree clustering
• Parametrized complexity theory.
• The complexity of satisfiability problems
• The directed subgraph homeomorphism problem
• Which problems have strongly exponential complexity?

Cited in

(9)

• Inferring (biological) signal transduction networks via transitive reductions of directed graphs
• Cluster editing
• Quantifying hierarchical conflicts in homology statements
• scientific article; zbMATH DE number 5237243 (Why is no real title available?)
• On Making Directed Graphs Transitive
• On the kernelization of ranking \(r\)-CSPs: linear vertex-kernels for generalizations of feedback arc set and betweenness in tournaments
• scientific article; zbMATH DE number 15035 (Why is no real title available?)
• A parameterized algorithmics framework for degree sequence completion problems in directed graphs
• Cluster editing with locally bounded modifications

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)