Cutwidth (English Wikipedia)

Analysis of information sources in references of the Wikipedia article "Cutwidth" in English language version.

refsWebsite

Global rank English rank

2^nd place

2^nd place

451^st place

277^th place

1,933^rd place

1,342^nd place

9,203^rd place

low place

741^st place

577^th place

low place

low place

102^nd place

76^th place

1semanticscholar.org

11^th place

8^th place

69^th place

59^th place

1,115^th place

741^st place

ams.org

mathscinet.ams.org

Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a tree" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 268–277. doi:10.1137/0606026. MR 0778007.
Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm" (PDF). Journal of Algorithms. 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. MR 2146375.
Korach, Ephraim; Solel, Nir (1993). "Tree-width, path-width, and cutwidth". Discrete Applied Mathematics. 43 (1): 97–101. doi:10.1016/0166-218X(93)90171-J. MR 1218045.
Chung, F. R. K.; Seymour, P. D. (1989). "Graphs with small bandwidth and cutwidth" (PDF). Discrete Mathematics. 75 (1–3): 113–119. doi:10.1016/0012-365X(89)90083-6. MR 1001391.
Makedon, Fillia; Sudborough, Ivan Hal (1989). "On minimizing width in linear layouts". Discrete Applied Mathematics. 23 (3): 243–265. doi:10.1016/0166-218X(89)90016-4. MR 0996137.
Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Crossing numbers and cutwidths". Journal of Graph Algorithms and Applications. 7 (3): 245–251. doi:10.7155/jgaa.00069. MR 2112230.
Stöhr, Elena (1988). "A trade-off between page number and page width of book embeddings of graphs". Information and Computation. 79 (2): 155–162. doi:10.1016/0890-5401(88)90036-3. MR 0968104.
Yannakakis, Mihalis (1985). "A polynomial algorithm for the min-cut linear arrangement of trees". Journal of the ACM. 32 (4): 950–988. doi:10.1145/4221.4228. MR 0810346.
Monien, B.; Sudborough, I. H. (1988). "Min cut is NP-complete for edge weighted trees". Theoretical Computer Science. 58 (1–3): 209–229. doi:10.1016/0304-3975(88)90028-X. MR 0963264.
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl:1956/4556. MR 2885638. S2CID 9967521.
Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Quantum speedups for exponential-time dynamic programming algorithms". In Chan, Timothy M. (ed.). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019. Society for Industrial and Applied Mathematics. pp. 1783–1793. arXiv:1807.05209. doi:10.1137/1.9781611975482.107. MR 3909576.
Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). "Cutwidth: obstructions and algorithmic aspects" (PDF). Algorithmica. 81 (2): 557–588. doi:10.1007/s00453-018-0424-7. MR 3910081.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002). "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems". Mathematical Programming. 92 (1, Ser. A): 1–36. doi:10.1007/s101070100271. MR 1892295.
Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of treewidth, one-shot pebbling, and related layout problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030. MR 3195329.
Leighton, Tom; Rao, Satish (1999). "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms". Journal of the ACM. 46 (6): 787–832. doi:10.1145/331524.331526. MR 1753034.
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning" (PDF). Journal of the ACM. 56 (2): Art. 5, 37. doi:10.1145/1502793.1502794. MR 2535878.
Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). "Fixed-parameter algorithms for protein similarity search under mRNA structure constraints". Journal of Discrete Algorithms. 6 (4): 618–626. doi:10.1016/j.jda.2008.03.004. MR 2463425.
Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). "Scheduling series-parallel task graphs to minimize peak memory". Theoretical Computer Science. 707: 1–23. doi:10.1016/j.tcs.2017.09.037. MR 3734396.
Fotouhi, Farshad; Pramanik, Sakti (1991). "Problem of optimizing the number of block accesses in performing relational join is NP-hard". Information Processing Letters. 38 (5): 271–275. doi:10.1016/0020-0190(91)90070-X. MR 1114421.
Morin, Pat; Wood, David R. (2004). "Three-dimensional 1-bend graph drawings". Journal of Graph Algorithms and Applications. 8 (3): 357–366. doi:10.7155/jgaa.00095. MR 2176967.

arxiv.org

Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Quantum speedups for exponential-time dynamic programming algorithms". In Chan, Timothy M. (ed.). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019. Society for Industrial and Applied Mathematics. pp. 1783–1793. arXiv:1807.05209. doi:10.1137/1.9781611975482.107. MR 3909576.

doi.org

Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a tree" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 268–277. doi:10.1137/0606026. MR 0778007.
Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm" (PDF). Journal of Algorithms. 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. MR 2146375.
Korach, Ephraim; Solel, Nir (1993). "Tree-width, path-width, and cutwidth". Discrete Applied Mathematics. 43 (1): 97–101. doi:10.1016/0166-218X(93)90171-J. MR 1218045.
Chung, F. R. K.; Seymour, P. D. (1989). "Graphs with small bandwidth and cutwidth" (PDF). Discrete Mathematics. 75 (1–3): 113–119. doi:10.1016/0012-365X(89)90083-6. MR 1001391.
Makedon, Fillia; Sudborough, Ivan Hal (1989). "On minimizing width in linear layouts". Discrete Applied Mathematics. 23 (3): 243–265. doi:10.1016/0166-218X(89)90016-4. MR 0996137.
Díaz, Josep; Petit, Jordi; Serna, Maria (September 2002). "A survey of graph layout problems" (PDF). ACM Computing Surveys. 34 (3): 313–356. doi:10.1145/568522.568523.
Seymour, Paul D.; Thomas, Robin (1994). "Call routing and the ratcatcher". Combinatorica. 14 (2): 217–241. doi:10.1007/BF01215352.
Djidjev, Hristo N.; Vrt'o, Imrich (2003). "Crossing numbers and cutwidths". Journal of Graph Algorithms and Applications. 7 (3): 245–251. doi:10.7155/jgaa.00069. MR 2112230.
Stöhr, Elena (1988). "A trade-off between page number and page width of book embeddings of graphs". Information and Computation. 79 (2): 155–162. doi:10.1016/0890-5401(88)90036-3. MR 0968104.
Yannakakis, Mihalis (1985). "A polynomial algorithm for the min-cut linear arrangement of trees". Journal of the ACM. 32 (4): 950–988. doi:10.1145/4221.4228. MR 0810346.
Monien, B.; Sudborough, I. H. (1988). "Min cut is NP-complete for edge weighted trees". Theoretical Computer Science. 58 (1–3): 209–229. doi:10.1016/0304-3975(88)90028-X. MR 0963264.
Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl:1956/4556. MR 2885638. S2CID 9967521.
Ambainis, Andris; Balodis, Kaspars; Iraids, Jānis; Kokainis, Martins; Prūsis, Krišjānis; Vihrovs, Jevgēnijs (2019). "Quantum speedups for exponential-time dynamic programming algorithms". In Chan, Timothy M. (ed.). Proceedings of the Thirtieth Annual ACM–SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6–9, 2019. Society for Industrial and Applied Mathematics. pp. 1783–1793. arXiv:1807.05209. doi:10.1137/1.9781611975482.107. MR 3909576.
Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). "Cutwidth: obstructions and algorithmic aspects" (PDF). Algorithmica. 81 (2): 557–588. doi:10.1007/s00453-018-0424-7. MR 3910081.{{cite journal}}: CS1 maint: multiple names: authors list (link)
Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket (2008). "Graph layout problems parameterized by vertex cover" (PDF). In Hong, Seok-Hee; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings. Lecture Notes in Computer Science. Vol. 5369. Springer. pp. 294–305. doi:10.1007/978-3-540-92182-0_28.
Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002). "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems". Mathematical Programming. 92 (1, Ser. A): 1–36. doi:10.1007/s101070100271. MR 1892295.
Wu, Yu; Austrin, Per; Pitassi, Toniann; Liu, David (2014). "Inapproximability of treewidth, one-shot pebbling, and related layout problems". Journal of Artificial Intelligence Research. 49: 569–600. doi:10.1613/jair.4030. MR 3195329.
Leighton, Tom; Rao, Satish (1999). "Multicommodity max-flow min-cut theorems and their use in designing approximation algorithms". Journal of the ACM. 46 (6): 787–832. doi:10.1145/331524.331526. MR 1753034.
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning" (PDF). Journal of the ACM. 56 (2): Art. 5, 37. doi:10.1145/1502793.1502794. MR 2535878.
Blin, Guillaume; Fertin, Guillaume; Hermelin, Danny; Vialette, Stéphane (2008). "Fixed-parameter algorithms for protein similarity search under mRNA structure constraints". Journal of Discrete Algorithms. 6 (4): 618–626. doi:10.1016/j.jda.2008.03.004. MR 2463425.
Kayaaslan, Enver; Lambert, Thomas; Marchal, Loris; Uçar, Bora (2018). "Scheduling series-parallel task graphs to minimize peak memory". Theoretical Computer Science. 707: 1–23. doi:10.1016/j.tcs.2017.09.037. MR 3734396.
Fotouhi, Farshad; Pramanik, Sakti (1991). "Problem of optimizing the number of block accesses in performing relational join is NP-hard". Information Processing Letters. 38 (5): 271–275. doi:10.1016/0020-0190(91)90070-X. MR 1114421.
Morin, Pat; Wood, David R. (2004). "Three-dimensional 1-bend graph drawings". Journal of Graph Algorithms and Applications. 8 (3): 357–366. doi:10.7155/jgaa.00095. MR 2176967.

handle.net

hdl.handle.net

Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl:1956/4556. MR 2885638. S2CID 9967521.

princeton.edu

cs.princeton.edu

Arora, Sanjeev; Frieze, Alan; Kaplan, Haim (2002). "A new rounding procedure for the assignment problem with applications to dense graph arrangement problems". Mathematical Programming. 92 (1, Ser. A): 1–36. doi:10.1007/s101070100271. MR 1892295.
Arora, Sanjeev; Rao, Satish; Vazirani, Umesh (2009). "Expander flows, geometric embeddings and graph partitioning" (PDF). Journal of the ACM. 56 (2): Art. 5, 37. doi:10.1145/1502793.1502794. MR 2535878.

semanticscholar.org

api.semanticscholar.org

Bodlaender, Hans L.; Fomin, Fedor V.; Koster, Arie M. C. A.; Kratsch, Dieter; Thilikos, Dimitrios M. (2012). "A note on exact algorithms for vertex ordering problems on graphs". Theory of Computing Systems. 50 (3): 420–432. doi:10.1007/s00224-011-9312-0. hdl:1956/4556. MR 2885638. S2CID 9967521.

ucsb.edu

sites.cs.ucsb.edu

Fellows, Michael R.; Lokshtanov, Daniel; Misra, Neeldhara; Rosamond, Frances A.; Saurabh, Saket (2008). "Graph layout problems parameterized by vertex cover" (PDF). In Hong, Seok-Hee; Nagamochi, Hiroshi; Fukunaga, Takuro (eds.). Algorithms and Computation, 19th International Symposium, ISAAC 2008, Gold Coast, Australia, December 15–17, 2008, Proceedings. Lecture Notes in Computer Science. Vol. 5369. Springer. pp. 294–305. doi:10.1007/978-3-540-92182-0_28.

ucsd.edu

mathweb.ucsd.edu

Chung, Fan R. K. (1985). "On the cutwidth and the topological bandwidth of a tree" (PDF). SIAM Journal on Algebraic and Discrete Methods. 6 (2): 268–277. doi:10.1137/0606026. MR 0778007.
Chung, F. R. K.; Seymour, P. D. (1989). "Graphs with small bandwidth and cutwidth" (PDF). Discrete Mathematics. 75 (1–3): 113–119. doi:10.1016/0012-365X(89)90083-6. MR 1001391.

uoa.gr

users.uoa.gr

Thilikos, Dimitrios M.; Serna, Maria; Bodlaender, Hans L. (2005). "Cutwidth I: A linear time fixed parameter algorithm" (PDF). Journal of Algorithms. 56 (1): 1–24. doi:10.1016/j.jalgor.2004.12.001. MR 2146375.
Giannopoulou, Archontia C.; Pilipczuk, Jean-Florent, Michałand Raymond; Thilikos, Dimitrios M.; Wrochna, Marcin (2019). "Cutwidth: obstructions and algorithmic aspects" (PDF). Algorithmica. 81 (2): 557–588. doi:10.1007/s00453-018-0424-7. MR 3910081.{{cite journal}}: CS1 maint: multiple names: authors list (link)

upc.edu

cs.upc.edu

Díaz, Josep; Petit, Jordi; Serna, Maria (September 2002). "A survey of graph layout problems" (PDF). ACM Computing Surveys. 34 (3): 313–356. doi:10.1145/568522.568523.