On the algorithmic effectiveness of digraph decompositions and complexity measures

DOI10.1016/j.disopt.2010.03.010zbMath1248.90073OpenAlexW2149379116MaRDI QIDQ456704

Georgia Kaouri, Valia Mitsou, Michael Lampis

Publication date: 16 October 2012

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2010.03.010

zbMATH Keywords

treewidthparameterized complexitydigraph decompositions

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Abstract computational complexity for mathematical programming problems (90C60)

Related Items (10)

An algorithmic metatheorem for directed treewidth ⋮ Impact of soft ride time constraints on the complexity of scheduling in dial-a-ride problems ⋮ Directed elimination games ⋮ Unnamed Item ⋮ Digraph width measures in parameterized algorithmics ⋮ Approximation algorithms for digraph width parameters ⋮ An LP-rounding \(2\sqrt{2}\)-approximation for restricted maximum acyclic subgraph ⋮ Unnamed Item ⋮ A sub-exponential FPT algorithm and a polynomial kernel for minimum directed bisection on semicomplete digraphs ⋮ Computations by fly-automata beyond monadic second-order logic

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On miniaturized problems in parameterized complexity theory
• On complexity of minimum leaf out-branching problem
• Optimization, approximation, and complexity classes
• Graph searching and a min-max theorem for tree-width
• Fugitive-search games on graphs and related parameters
• Directed tree-width
• Directed path-width and monotonicity in digraph searching
• Transition graphs and the star-height of regular events
• The monadic second-order logic of graphs. I: Recognizable sets of finite graphs
• Finite Automata, Digraph Connectivity, and Regular Expression Size
• Treewidth: Characterizations, Applications, and Computations
• DAG-width
• On Digraph Width Measures in Parameterized Algorithmics
• Graph minors. II. Algorithmic aspects of tree-width
• An algebraic theory of graph reduction
• Digraph Decompositions and Monotonicity in Digraph Searching
• Treewidth: Structure and Algorithms

This page was built for publication: On the algorithmic effectiveness of digraph decompositions and complexity measures