Konstantin Makarychev, and Yury Makarychev. o( ( log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems, 37th Annual ACM Symposium on Theory of Computing, pp.573-581, 2005. ,
Rank numbers of grid graphs, Discrete Mathematics, vol.310, issue.23, pp.3103324-3333, 2010. ,
DOI : 10.1016/j.disc.2010.07.022
Inference of Reversible Languages, Journal of the ACM, vol.29, issue.3, pp.741-765, 1982. ,
DOI : 10.1145/322326.322334
Ordered coloring of grids and related graphs, Theoretical Computer Science, vol.444, pp.40-51, 2012. ,
DOI : 10.1016/j.tcs.2012.04.036
Directed Path-width and Monotonicity in Digraph Searching, Graphs and Combinatorics, vol.22, issue.2, pp.161-172, 2006. ,
DOI : 10.1007/s00373-005-0627-y
The dag-width of directed graphs, Journal of Combinatorial Theory, Series B, vol.102, issue.4, pp.900-923, 2012. ,
DOI : 10.1016/j.jctb.2012.04.004
The traveling salesman problem in bounded degree graphs, ACM Transactions on Algorithms, vol.8, issue.2, p.18, 2012. ,
DOI : 10.1145/2151171.2151181
Approximating treewidth, pathwidth , frontsize, and shortest elimination tree, Journal of Algorithms, vol.18, issue.2, pp.238-255, 1995. ,
A fixed-parameter algorithm for the directed feedback vertex set problem, Journal of the ACM, vol.55, issue.5, 2008. ,
Transition graphs and the star height of regular events, pp.385-397, 1963. ,
The theory of elimination trees for sparse unsymmetric matrices, SIAM Journal on Matrix Analysis and Applications, vol.26, issue.3, pp.686-705, 2005. ,
Exact Exponential Algorithms. Texts in Theoretical Computer Science. An EATCS Series, 2010. ,
On Digraph Width Measures in Parameterized Algorithmics, 4th International Workshop on Parameterized and Exact Computation, pp.185-197, 2009. ,
DOI : 10.1007/978-3-642-11269-0_15
Computers and Intractability: A Guide to the Theory of NP- Completeness. A Series of Books in the Mathematical Sciences, 1979. ,
Digraph complexity measures and applications in formal language theory, Mathematical and Engineering Methods in Computer Science, pp.60-67, 2008. ,
URL : https://hal.archives-ouvertes.fr/hal-00990597
On balanced separators, treewidth, and cycle rank, Journal of Combinatorics, vol.3, issue.4 ,
DOI : 10.4310/JOC.2012.v3.n4.a5
Finite Automata, Digraph Connectivity, and Regular Expression Size, 35th International Colloquium on Automata, Languages and Programming (Part II), pp.39-50, 2008. ,
DOI : 10.1007/978-3-540-70583-3_4
Algorithms for determining relative star height and star height, Information and Computation, vol.78, issue.2, pp.124-169, 1988. ,
DOI : 10.1016/0890-5401(88)90033-8
NONDETERMINISTIC DESCRIPTIONAL COMPLEXITY OF REGULAR LANGUAGES, International Journal of Foundations of Computer Science, vol.14, issue.06, pp.1087-1102, 2003. ,
DOI : 10.1142/S0129054103002199
Introduction to Automata Theory, Languages and Computation, Series in Computer Science, 1979. ,
LIFO-Search on Digraphs: A Searching Game for Cycle-Rank, 18th International Symposium on Fundamentals of Computation Theory, pp.217-228, 2011. ,
DOI : 10.1006/jctb.1993.1027
Computational parallels between the regular and context-free languages, SIAM Journal on Computing, vol.7, issue.1, pp.99-114, 1978. ,
Approximation algorithms for directed width parameters Available online as arXiv:1107, 2011. ,
On the complexity of the relative inclusion star height problem, Advances in Computer Science and Engineering, vol.5, issue.3, pp.173-211, 2010. ,
Digraph decompositions and monotonicity in digraph searching, Theoretical Computer Science, vol.412, issue.35, pp.4688-4703, 2011. ,
DOI : 10.1016/j.tcs.2011.05.003
On the algorithmic effectiveness of digraph decompositions and complexity measures, Discrete Optimization, vol.8, issue.1, pp.129-138, 2011. ,
DOI : 10.1016/j.disopt.2010.03.010
The loop complexity of pure-group events, Information and Control, vol.11, issue.1-2, pp.167-176, 1967. ,
DOI : 10.1016/S0019-9958(67)90481-0
The loop complexity of regular events, Information Sciences, vol.1, issue.3, pp.305-328, 1969. ,
DOI : 10.1016/S0020-0255(69)80016-2
Tree-depth, subgraph coloring and homomorphism bounds, European Journal of Combinatorics, vol.27, issue.6, pp.1022-1041, 2006. ,
DOI : 10.1016/j.ejc.2005.01.010
Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques, Theory of Computing Systems, vol.41, issue.3, pp.563-587, 2007. ,
DOI : 10.1007/s00224-007-1334-2
Computing minimum directed feedback vertex set in O * (1.9977 n ), Proceedings of the 10th Italian Conference on Theoretical Computer Science, pp.70-81, 2007. ,
Graph minors. II. Algorithmic aspects of tree-width, Journal of Algorithms, vol.7, issue.3, pp.309-322, 1986. ,
DOI : 10.1016/0196-6774(86)90023-4
D-Width: A more natural measure for directed tree width, 30th International Symposium on Mathematical Foundations of Computer Science, pp.745-756, 2005. ,
A New Implementation of Sparse Gaussian Elimination, ACM Transactions on Mathematical Software, vol.8, issue.3, pp.256-276, 1982. ,
DOI : 10.1145/356004.356006
On enumerating all minimal solutions of feedback problems, Discrete Applied Mathematics, vol.117, issue.1-3, pp.253-265, 2002. ,
DOI : 10.1016/S0166-218X(00)00339-5
Irreducibility of multivariate polynomials, Journal of Computer and System Sciences, vol.31, issue.2, pp.225-264, 1985. ,
A digraph G and an integer k ,
Approximable within O((log n) 3/2 ) in polynomial time (Thm. 13) Exact solution can be computed in time O * (1.9129 n ) for digraphs with maximum outdegree at most 2; and for unbounded outdegree in time O * ,
For digraphs with maximum outdegree at most 2, exact solution can be computed in time O * (1.9129 n ) (Thm. 17); and in time O * (1.9977 n ) for unbounded outdegree ,
Approximable within O((log n) 3/2 ) in polynomial time (Thm. 21) Exact solution can be computed in time O * (1.9129 n ) for binary alphabets; and for unbounded alphabet size in time O * ,
NP-complete; NP-hardness holds already for binary alphabets (Thm ,
Problem is decidable [20]. Exact solution can be computed within exponential space and doubly exponential time ,
NP-hard, already for binary alphabets (Thm. 23) Problem is PSPACE-hard if input given by an nondeterministic finite automaton in place of a deterministic one ,