Efficient algorithms for measuring the funnel-likeness of DAGs

DOI10.1007/978-3-319-96151-4_16zbMath1404.90133arXiv1801.10401OpenAlexW2962677009WikidataQ126863544 ScholiaQ126863544MaRDI QIDQ5915704

Marcelo Garlet Millani, Rolf Niedermeier, Manuel Sorge, Hendrik Molter

Publication date: 17 August 2018

Published in: Lecture Notes in Computer Science, Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1801.10401

zbMATH Keywords

experimentsdirected graphsapproximation algorithmsNP-hard problemsfixed-parameter tractabilityacyclic digraphgraph parametersapproximation hardness

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Analysis of algorithms and problem complexity (68Q25) Combinatorial optimization (90C27) Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Directed graphs (digraphs), tournaments (05C20)

Related Items (5)

A polynomial kernel for funnel arc deletion set ⋮ Safety and completeness in flow decompositions for RNA assembly ⋮ A Polynomial Kernel for Funnel Arc Deletion Set. ⋮ Efficient algorithms for measuring the funnel-likeness of DAGs ⋮ Linear time algorithms on mirror trees

Uses Software

• KONECT

Cites Work

• Unnamed Item
• Fundamentals of parameterized complexity
• Fixed-parameter algorithms for DAG partitioning
• Kernels for feedback arc set in tournaments
• Are there any good digraph width measures?
• The directed subgraph homeomorphism problem
• Which problems have strongly exponential complexity?
• Kernels for deletion to classes of acyclic digraphs
• Polynomial kernels for deletion to classes of acyclic digraphs
• Parameterized complexity of vertex colouring
• Directed tree-width
• Fixed-parameter tractability results for feedback set problems in tournaments
• Parameterised algorithms for deletion to classes of DAGs
• Digraph width measures in parameterized algorithmics
• Hardness of fully dense problems
• Reflections on Multivariate Algorithmics and Problem Parameterization
• A threshold of ln n for approximating set cover
• The Minimum Feedback Arc Set Problem is NP-Hard for Tournaments
• A fixed-parameter algorithm for the directed feedback vertex set problem
• Classes of Directed Graphs
• The approximation of maximum subgraph problems
• Directed Subset Feedback Vertex Set Is Fixed-Parameter Tractable
• Feedback Vertex Set in Mixed Graphs
• Parameterized and Exact Computation
• Digraphs
• Efficient algorithms for measuring the funnel-likeness of DAGs
• On the complexity of \(k\)-SAT

This page was built for publication: Efficient algorithms for measuring the funnel-likeness of DAGs