nach oben

Erschienen in:

2019 | OriginalPaper | Buchkapitel

Computing Digraph Width Measures on Directed Co-graphs

(Extended Abstract)

verfasst von : Frank Gurski, Dominique Komander, Carolin Rehs

Erschienen in: Fundamentals of Computation Theory

Verlag: Springer International Publishing

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

Abstract

In this paper we consider the digraph width measures directed feedback vertex set number, cycle rank, DAG-depth, DAG-width and Kelly-width. While the minimization problem for these width measures is generally NP-hard, we prove that it is computable in linear time for all these parameters, except for Kelly-width, when restricted to directed co-graphs. As an important combinatorial tool, we show how these measures can be computed for the disjoint union, series composition, and order composition of two directed graphs, which further leads to some similarities and a good comparison between the width measures. This generalizes and expands our former results for computing directed path-width and directed tree-width of directed co-graphs.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Maximum Rectilinear Convex Subsets

Nächstes Kapitel Fault-Tolerant Parallel Scheduling of Arbitrary Length Jobs on a Shared Channel

There are also further directed tree-width definitions such as allowing empty sets \(W_r\) in [23], using sets \(W_r\) of size one only for the leaves of T in [29] and using strong components within (dtw-2) in [13, Chap. 6]. Further in works of Courcelle et al. [9‐11] the directed tree-width of a digraph G is defined by the tree-width of the underlying undirected graph. One reason for this could be the algorithmic advantages of the undirected tree-width.

A remarkable difference to the undirected tree-width from [30] is that the sets \(W_r\) have to be disjoint and non-empty.

XP is the class of all parameterized problems that can be solved in a certain time, see [14] for a definition.

The proofs of the results marked with a \(\bigstar \) are omitted due to space restrictions.

In the undirected case, reachable fragments coincide with connected components.

Amiri, S.A., Kreutzer, S., Rabinovich, R.: DAG-width is PSPACE-complete. Theor. Comput. Sci. 655, 78–89 (2016)MathSciNetCrossRef

Arnborg, S., Corneil, D.G., Proskurowski, A.: Complexity of finding embeddings in a \(k\)-tree. SIAM J. Algebr. Discrete Methods 8(2), 277–284 (1987)MathSciNetCrossRef

Bang-Jensen, J., Gutin, G.: Digraphs. Theory, Algorithms and Applications. Springer, Heidelberg (2009). https://doi.org/10.1007/978-1-84800-998-1CrossRefMATH

Bechet, D., de Groote, P., Retoré, C.: A complete axiomatisation for the inclusion of series-parallel partial orders. In: Comon, H. (ed.) RTA 1997. LNCS, vol. 1232, pp. 230–240. Springer, Heidelberg (1997). https://doi.org/10.1007/3-540-62950-5_74CrossRef

Berwanger, D., Dawar, A., Hunter, P., Kreutzer, S.: DAG-width and parity games. In: Durand, B., Thomas, W. (eds.) STACS 2006. LNCS, vol. 3884, pp. 524–536. Springer, Heidelberg (2006). https://doi.org/10.1007/11672142_43CrossRef

Berwangera, D., Dawar, A., Hunter, P., Kreutzer, S., Obdrzálek, J.: The dag-width of directed graphs. J. Comb. Theory Ser. B 102(4), 900–923 (2012)MathSciNetCrossRef

Bodlaender, H.L., Möhring, R.H.: The pathwidth and treewidth of cographs. SIAM J. Disc. Math. 6(2), 181–188 (1993)MathSciNetCrossRef

Cohen, R.S.: Transition graphs and the star height problem. In: Proceedings of the 9th Annual Symposium on Switching and Automata Theory, pp. 383–394. IEEE Computer Society (1968)

Courcelle, B.: From tree-decompositions to clique-width terms. Discrete Appl. Math. 248, 125–144 (2018)MathSciNetCrossRef

10.

Courcelle, B., Engelfriet, J.: Graph Structure and Monadic Second-Order Logic. A Language-Theoretic Approach. Encyclopedia of Mathematics and its Applications. Cambridge University Press, Cambridge (2012)CrossRef

11.

Courcelle, B., Olariu, S.: Upper bounds to the clique width of graphs. Discrete Appl. Math. 101, 77–114 (2000)MathSciNetCrossRef

12.

Crespelle, C., Paul, C.: Fully dynamic recognition algorithm and certificate for directed cographs. Discrete Appl. Math. 154(12), 1722–1741 (2006)MathSciNetCrossRef

13.

Dehmer, M., Emmert-Streib, F. (eds.): Quantitative Graph Theory: Mathematical Foundations and Applications. CRC Press Inc., New York (2014)MATH

14.

Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Springer, Heidelberg (2013). https://doi.org/10.1007/978-1-4471-5559-1CrossRefMATH

15.

Eggan, L.E.: Transition graphs and the star height of regular events. Michigan Math. J. 10, 385–397 (1963)MathSciNetCrossRef

16.

Ganian, R., Hliněný, P., Kneis, J., Langer, A., Obdržálek, J., Rossmanith, P.: On digraph width measures in parameterized algorithmics. In: Chen, J., Fomin, F.V. (eds.) IWPEC 2009. LNCS, vol. 5917, pp. 185–197. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-11269-0_15CrossRefMATH

17.

Ganian, R., Hlinený, P., Kneis, J., Langer, A., Obdrzálek, J., Rossmanith, P.: Digraph width measures in parameterized algorithmics. Discrete Appl. Math. 168, 88–107 (2014)MathSciNetCrossRef

18.

Ganian, R., et al.: Are there any good digraph width measures? J. Comb. Theory Ser. B 116, 250–286 (2016)MathSciNetCrossRef

19.

Gruber, H.: Digraph complexity measures and applications in formal language theory. Discret. Math. Theor. Comput. Sci. 14(2), 189–204 (2012)MathSciNetMATH

20.

Gurski, F., Rehs, C.: Computing directed path-width and directed tree-width of recursively defined digraphs. ACM Computing Research Repository (CoRR), abs/1806.04457, 16 p. (2018)

21.

Gurski, F., Rehs, C.: Directed path-width and directed tree-width of directed co-graphs. In: Wang, L., Zhu, D. (eds.) COCOON 2018. LNCS, vol. 10976, pp. 255–267. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-94776-1_22CrossRefMATH

22.

Hunter, P., Kreutzer, S.: Digraph measures: Kelly decompositions, games, and orderings. Theor. Comput. Sci. 399(3), 206–219 (2008)MathSciNetCrossRef

23.

Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Addentum to “Directed tree-width” (2001)MathSciNetCrossRef

24.

Johnson, T., Robertson, N., Seymour, P.D., Thomas, R.: Directed tree-width. J. Comb. Theory Ser. B 82, 138–155 (2001)MathSciNetCrossRef

25.

McNaughton, R.: The loop complexity of regular events. Inf. Sci. 1(3), 305–328 (1969)MathSciNetCrossRef

26.

Monien, B., Sudborough, I.H.: Min cut is NP-complete for edge weighted trees. Theor. Comput. Sci. 58, 209–229 (1988)MathSciNetCrossRef

27.

Nešetřil, J., de Mendez, P.O.: Tree-depth, subgraph coloring and homomorphism bounds. Eur. J. Comb. 27, 1022–1041 (2006)MathSciNetCrossRef

28.

Obdrzálek, J.: Dag-width: connectivity measure for directed graphs. In: Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 814–821. ACM-SIAM (2006)

29.

Reed, B.: Introducing directed tree width. Electron. Notes Discret. Math. 3, 222–229 (1999)MathSciNetCrossRef

30.

Robertson, N., Seymour, P.D.: Graph minors II. Algorithmic aspects of tree width. J. Algorithms 7, 309–322 (1986)MathSciNetCrossRef

Titel: Computing Digraph Width Measures on Directed Co-graphs
verfasst von: Frank Gurski
Dominique Komander
Carolin Rehs
Verlag: Springer International Publishing
Buch: Fundamentals of Computation Theory
Print ISBN: 978-3-030-25026-3

Electronic ISBN: 978-3-030-25027-0

Copyright-Jahr: 2019
DOI: https://doi.org/10.1007/978-3-030-25027-0_20

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner