Bachtler, Oliver; Bergner, Tim; Krumke, Sven O. Almost disjoint paths and separating by forbidden pairs. (English) Zbl 07809110 Theor. Comput. Sci. 982, Article ID 114272, 20 p. (2024). MSC: 68Qxx PDFBibTeX XMLCite \textit{O. Bachtler} et al., Theor. Comput. Sci. 982, Article ID 114272, 20 p. (2024; Zbl 07809110) Full Text: DOI arXiv
Bekos, Michael A.; Da Lozzo, Giordano; Frati, Fabrizio; Gronemann, Martin; Mchedlidze, Tamara; Raftopoulou, Chrysanthi N. Recognizing DAGs with page-number 2 is NP-complete. (English) Zbl 1512.68190 Theor. Comput. Sci. 946, Article ID 113689, 11 p. (2023). MSC: 68R10 68Q17 PDFBibTeX XMLCite \textit{M. A. Bekos} et al., Theor. Comput. Sci. 946, Article ID 113689, 11 p. (2023; Zbl 1512.68190) Full Text: DOI arXiv
Ingels, Florian; Azaïs, Romain Enumeration of irredundant forests. (English) Zbl 07540214 Theor. Comput. Sci. 922, 312-334 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{F. Ingels} and \textit{R. Azaïs}, Theor. Comput. Sci. 922, 312--334 (2022; Zbl 07540214) Full Text: DOI arXiv
Kim, Yonghwan; Shibata, Masahiro; Sudo, Yuichi; Nakamura, Junya; Katayama, Yoshiaki; Masuzawa, Toshimitsu A self-stabilizing algorithm for constructing a minimal reachable directed acyclic graph with two senders and two targets. (English) Zbl 1504.68173 Theor. Comput. Sci. 874, 1-14 (2021). MSC: 68R10 PDFBibTeX XMLCite \textit{Y. Kim} et al., Theor. Comput. Sci. 874, 1--14 (2021; Zbl 1504.68173) Full Text: DOI
Bang-Jensen, J.; Bellitto, T.; Lochet, W.; Yeo, A. The directed 2-linkage problem with length constraints. (English) Zbl 1445.68146 Theor. Comput. Sci. 814, 69-73 (2020). Reviewer: K. Subramani (Morgantown) MSC: 68R10 05C20 05C38 68Q25 PDFBibTeX XMLCite \textit{J. Bang-Jensen} et al., Theor. Comput. Sci. 814, 69--73 (2020; Zbl 1445.68146) Full Text: DOI arXiv Link
Chen, Yong; Goebel, Randy; Lin, Guohui; Su, Bing; Zhang, An Open-shop scheduling for unit jobs under precedence constraints. (English) Zbl 1436.90047 Theor. Comput. Sci. 803, 144-151 (2020). Reviewer: Sigrid Knust (Osnabrück) MSC: 90B35 68W25 PDFBibTeX XMLCite \textit{Y. Chen} et al., Theor. Comput. Sci. 803, 144--151 (2020; Zbl 1436.90047) Full Text: DOI
Wallner, Michael A bijection of plane increasing trees with relaxed binary trees of right height at most one. (English) Zbl 1441.05051 Theor. Comput. Sci. 755, 1-12 (2019). MSC: 05C05 05C10 05C78 05C30 11B39 PDFBibTeX XMLCite \textit{M. Wallner}, Theor. Comput. Sci. 755, 1--12 (2019; Zbl 1441.05051) Full Text: DOI arXiv
da Silva, Rodrigo Ferreira; Urrutia, Sebastián; dos Santos, Vinícius Fernandes One-sided weak dominance drawing. (English) Zbl 1422.68186 Theor. Comput. Sci. 757, 36-43 (2019). Reviewer: K. Subramani (Morgantown, WV) MSC: 68R10 05C20 05C62 68Q17 68Q25 68W25 PDFBibTeX XMLCite \textit{R. F. da Silva} et al., Theor. Comput. Sci. 757, 36--43 (2019; Zbl 1422.68186) Full Text: DOI
Gaspers, Serge; Koivisto, Mikko; Liedloff, Mathieu; Ordyniak, Sebastian; Szeider, Stefan On finding optimal polytrees. (English) Zbl 1330.68223 Theor. Comput. Sci. 592, 49-58 (2015). MSC: 68R10 05B35 68Q17 68Q25 PDFBibTeX XMLCite \textit{S. Gaspers} et al., Theor. Comput. Sci. 592, 49--58 (2015; Zbl 1330.68223) Full Text: DOI arXiv
Fédou, Jean-Marc; Fici, Gabriele Vertical representation of \(\mathbf{C}^\infty\)-words. (English) Zbl 1314.68250 Theor. Comput. Sci. 565, 90-101 (2015). MSC: 68R15 05C90 PDFBibTeX XMLCite \textit{J.-M. Fédou} and \textit{G. Fici}, Theor. Comput. Sci. 565, 90--101 (2015; Zbl 1314.68250) Full Text: DOI arXiv
Hell, Pavol; Mishra, Aurosish \(H\)-coloring degree-bounded (acyclic) digraphs. (English) Zbl 1382.68112 Theor. Comput. Sci. 554, 40-49 (2014). MSC: 68Q25 05C15 05C20 05C85 68Q17 PDFBibTeX XMLCite \textit{P. Hell} and \textit{A. Mishra}, Theor. Comput. Sci. 554, 40--49 (2014; Zbl 1382.68112) Full Text: DOI
Milanič, Martin; Rizzi, Romeo; Tomescu, Alexandru I. Set graphs. II. Complexity of set graph recognition and similar problems. (English) Zbl 1298.05146 Theor. Comput. Sci. 547, 70-81 (2014). MSC: 05C20 05C62 05C69 68Q17 68Q25 PDFBibTeX XMLCite \textit{M. Milanič} et al., Theor. Comput. Sci. 547, 70--81 (2014; Zbl 1298.05146) Full Text: DOI arXiv
Takaoka, Tadao Sharing information for the all pairs shortest path problem. (English) Zbl 1358.05288 Theor. Comput. Sci. 520, 43-50 (2014). MSC: 05C85 05C38 05C35 05C20 68W40 PDFBibTeX XMLCite \textit{T. Takaoka}, Theor. Comput. Sci. 520, 43--50 (2014; Zbl 1358.05288) Full Text: DOI
Bermond, Jean-Claude; Cosnard, Michel; Pérennes, Stéphane Directed acyclic graphs with the unique dipath property. (English) Zbl 1301.05144 Theor. Comput. Sci. 504, 5-11 (2013). MSC: 05C20 05C78 05C15 PDFBibTeX XMLCite \textit{J.-C. Bermond} et al., Theor. Comput. Sci. 504, 5--11 (2013; Zbl 1301.05144) Full Text: DOI
Dash, Santanu Kumar; Scholz, Sven-Bodo; Herhut, Stephan; Christianson, Bruce A scalable approach to computing representative lowest common ancestor in directed acyclic graphs. (English) Zbl 1407.68351 Theor. Comput. Sci. 513, 25-37 (2013). MSC: 68R10 05C20 05C85 PDFBibTeX XMLCite \textit{S. K. Dash} et al., Theor. Comput. Sci. 513, 25--37 (2013; Zbl 1407.68351) Full Text: DOI
Tholey, Torsten Linear time algorithms for two disjoint paths problems on directed acyclic graphs. (English) Zbl 1256.68133 Theor. Comput. Sci. 465, 35-48 (2012). MSC: 68R10 05C85 68P05 PDFBibTeX XMLCite \textit{T. Tholey}, Theor. Comput. Sci. 465, 35--48 (2012; Zbl 1256.68133) Full Text: DOI
Acuña, Vicente; Birmelé, Etienne; Cottret, Ludovic; Crescenzi, Pierluigi; Jourdan, Fabien; Lacroix, Vincent; Marchetti-Spaccamela, Alberto; Marino, Andrea; Milreu, Paulo Vieira; Sagot, Marie-France; Stougie, Leen Telling stories: enumerating maximal directed acyclic graphs with a constrained set of sources and targets. (English) Zbl 1251.05079 Theor. Comput. Sci. 457, 1-9 (2012). MSC: 05C30 05C20 PDFBibTeX XMLCite \textit{V. Acuña} et al., Theor. Comput. Sci. 457, 1--9 (2012; Zbl 1251.05079) Full Text: DOI
Bentz, Cédric On the hardness of finding near-optimal multicuts in directed acyclic graphs. (English) Zbl 1222.68086 Theor. Comput. Sci. 412, No. 39, 5325-5332 (2011). MSC: 68Q25 68R10 05C20 90C27 PDFBibTeX XMLCite \textit{C. Bentz}, Theor. Comput. Sci. 412, No. 39, 5325--5332 (2011; Zbl 1222.68086) Full Text: DOI
Fujiyoshi, Akio Recognition of directed acyclic graphs by spanning tree automata. (English) Zbl 1207.68185 Theor. Comput. Sci. 411, No. 38-39, 3493-3506 (2010). MSC: 68Q45 68R10 PDFBibTeX XMLCite \textit{A. Fujiyoshi}, Theor. Comput. Sci. 411, No. 38--39, 3493--3506 (2010; Zbl 1207.68185) Full Text: DOI
Gutin, Gregory; Razgon, Igor; Kim, Eun Jung Minimum leaf out-branching and related problems. (English) Zbl 1343.68183 Theor. Comput. Sci. 410, No. 45, 4571-4579 (2009). MSC: 68R10 05C20 05C85 68Q17 68Q25 PDFBibTeX XMLCite \textit{G. Gutin} et al., Theor. Comput. Sci. 410, No. 45, 4571--4579 (2009; Zbl 1343.68183) Full Text: DOI
Buss, Samuel R.; Hoffmann, Jan The NP-hardness of finding a directed acyclic graph for regular resolution. (English) Zbl 1145.03034 Theor. Comput. Sci. 396, No. 1-3, 271-276 (2008). MSC: 03F20 68Q17 PDFBibTeX XMLCite \textit{S. R. Buss} and \textit{J. Hoffmann}, Theor. Comput. Sci. 396, No. 1--3, 271--276 (2008; Zbl 1145.03034) Full Text: DOI
Yuster, Raphael All-pairs disjoint paths from a common ancestor in \(\widetilde O (n^\omega)\) time. (English) Zbl 1140.68054 Theor. Comput. Sci. 396, No. 1-3, 145-150 (2008). MSC: 68R10 05C85 PDFBibTeX XMLCite \textit{R. Yuster}, Theor. Comput. Sci. 396, No. 1--3, 145--150 (2008; Zbl 1140.68054) Full Text: DOI
Královič, R.; Ružička, P. Ranks of graphs: The size of acyclic orientation cover for deadlock-free packet routing. (English) Zbl 1162.90367 Theor. Comput. Sci. 374, No. 1-3, 203-213 (2007). MSC: 90B18 68R10 05C20 68M10 PDFBibTeX XMLCite \textit{R. Královič} and \textit{P. Ružička}, Theor. Comput. Sci. 374, No. 1--3, 203--213 (2007; Zbl 1162.90367) Full Text: DOI
Czumaj, Artur; Kowaluk, Mirosław; Lingas, Andrzej Faster algorithms for finding lowest common ancestors in directed acyclic graphs. (English) Zbl 1118.68102 Theor. Comput. Sci. 380, No. 1-2, 37-46 (2007). MSC: 68R10 05C20 05C38 05C85 68W40 PDFBibTeX XMLCite \textit{A. Czumaj} et al., Theor. Comput. Sci. 380, No. 1--2, 37--46 (2007; Zbl 1118.68102) Full Text: DOI
Troníček, Zdeněk; Shinohara, Ayumi The size of subsequence automaton. (English) Zbl 1101.68052 Theor. Comput. Sci. 341, No. 1-3, 379-384 (2005). MSC: 68Q45 PDFBibTeX XMLCite \textit{Z. Troníček} and \textit{A. Shinohara}, Theor. Comput. Sci. 341, No. 1--3, 379--384 (2005; Zbl 1101.68052) Full Text: DOI
Courcelle, Bruno The monadic second-order logic of graphs. XI: Hierarchical decompositions of connected graphs. (English) Zbl 0938.03015 Theor. Comput. Sci. 224, No. 1-2, 35-58 (1999). Reviewer: M.Steinby (Turku) MSC: 03B15 03C85 05C40 PDFBibTeX XMLCite \textit{B. Courcelle}, Theor. Comput. Sci. 224, No. 1--2, 35--58 (1999; Zbl 0938.03015) Full Text: DOI
Cicerone, Serafino; Frigioni, Daniele; Nanni, Umberto; Pugliese, Francesco A uniform approach to semi-dynamic problems on digraphs. (English) Zbl 0917.68087 Theor. Comput. Sci. 203, No. 1, 69-90 (1998). MSC: 68W15 PDFBibTeX XMLCite \textit{S. Cicerone} et al., Theor. Comput. Sci. 203, No. 1, 69--90 (1998; Zbl 0917.68087) Full Text: DOI
Klawe, Maria M. Shallow grates. (English) Zbl 0791.05047 Theor. Comput. Sci. 123, No. 2, 389-395 (1994). Reviewer: N.F.Quimpo (Manila) MSC: 05C20 68R10 05C38 PDFBibTeX XMLCite \textit{M. M. Klawe}, Theor. Comput. Sci. 123, No. 2, 389--395 (1994; Zbl 0791.05047) Full Text: DOI
Di Battista, Giuseppe; Tamassia, Roberto Algorithms for plane representations of acyclic digraphs. (English) Zbl 0678.68059 Theor. Comput. Sci. 61, No. 2-3, 175-198 (1988). Reviewer: B.McKay MSC: 68R10 05C10 05C20 PDFBibTeX XMLCite \textit{G. Di Battista} and \textit{R. Tamassia}, Theor. Comput. Sci. 61, No. 2--3, 175--198 (1988; Zbl 0678.68059) Full Text: DOI
Simon, Klaus An improved algorithm for transitive closure on acyclic digraphs. (English) Zbl 0656.68047 Theor. Comput. Sci. 58, No. 1-3, 325-346 (1988). Reviewer: M.Křivánek MSC: 68Q25 05C20 68R10 PDFBibTeX XMLCite \textit{K. Simon}, Theor. Comput. Sci. 58, No. 1--3, 325--346 (1988; Zbl 0656.68047) Full Text: DOI
Kirousis, Lefteris M.; Papadimitriou, Christos H. Searching and pebbling. (English) Zbl 0616.68064 Theor. Comput. Sci. 47, 205-218 (1986). Reviewer: J.Ebert MSC: 68R10 68Q25 68P10 05C20 PDFBibTeX XMLCite \textit{L. M. Kirousis} and \textit{C. H. Papadimitriou}, Theor. Comput. Sci. 47, 205--218 (1986; Zbl 0616.68064) Full Text: DOI
Lev, G.; Valiant, L. G. Size bounds for superconcentrators. (English) Zbl 0497.68022 Theor. Comput. Sci. 22, 233-251 (1983). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{G. Lev} and \textit{L. G. Valiant}, Theor. Comput. Sci. 22, 233--251 (1983; Zbl 0497.68022) Full Text: DOI
Schnitger, Georg A family of graphs with expensive depth-reduction. (English) Zbl 0485.68054 Theor. Comput. Sci. 18, 89-93 (1982). MSC: 68R10 05C20 PDFBibTeX XMLCite \textit{G. Schnitger}, Theor. Comput. Sci. 18, 89--93 (1982; Zbl 0485.68054) Full Text: DOI
Sethi, Ravi Pebble games for studying storage sharing. (English) Zbl 0479.68070 Theor. Comput. Sci. 19, 69-84 (1982). MSC: 68R99 PDFBibTeX XMLCite \textit{R. Sethi}, Theor. Comput. Sci. 19, 69--84 (1982; Zbl 0479.68070) Full Text: DOI
Meyer Auf Der Heide, Friedhelm A comparison of two variations of a pebble game on graphs. (English) Zbl 0454.05031 Theor. Comput. Sci. 13, 315-322 (1981). MSC: 05C20 05C05 90C05 91A24 68Q05 PDFBibTeX XMLCite \textit{F. Meyer Auf Der Heide}, Theor. Comput. Sci. 13, 315--322 (1981; Zbl 0454.05031) Full Text: DOI