Ohtsuki et al. (1979)使用區間厚度模擬VLSI一維佈局所需的軌道數,此佈局由網絡系統相互連接的模塊組成。在他們的模型中,頂點代表網,若兩網都連接到同一模塊,就將兩頂點由邊相連;也就是說,若將模塊與網視作超圖的結點與超邊,則由它們形成的圖就是超圖的線圖。這超圖的區間表示與着色描述了沿水平軌道(一種顏色對應一條軌道)系統的網的排列,使模塊可沿軌道以線性順序排列,並連接到相應的網。區間圖都是完美圖[47],表明這類最佳排列中,所需顏色數等於網圖的區間完備化的團數。
門矩陣佈局[48]是一種用於布爾邏輯電路的CMOS VLSI佈局。當中,信號沿「線」(垂直線段)傳播,而電路的每個門則由沿水平線段的一系列器件特徵構成。因此,代表門的水平線段須與代表門輸入輸出的線路的垂直線段交叉。與Ohtsuki et al. (1979)的佈局類似,通過計算以線路為頂點,以共享同一門的線對為邊的圖的徑寬,可以找到使排列線路的垂直軌道數最小的佈局。[49]這種算法方法也可為可程式邏輯陣列的摺疊問題建模。[50]
Alon, Noga; Seymour, Paul; Thomas, Robin, A separator theorem for graphs with an excluded minor and its applications, Proc. 22nd ACM Symp. on Theory of Computing (STOC 1990): 293–299, 1990, ISBN 0897913612, S2CID 17521329, doi:10.1145/100216.100254.
Amini, Omid; Huc, Florian; Pérennes, Stéphane, On the path-width of planar graphs, SIAM Journal on Discrete Mathematics, 2009, 23 (3): 1311–1316, doi:10.1137/060670146.
Arnborg, Stefan, Efficient algorithms for combinatorial problems on graphs with bounded decomposability – A survey, BIT, 1985, 25 (1): 2–23, S2CID 122263659, doi:10.1007/BF01934985.
Arnborg, Stefan; Corneil, Derek G.; Proskurowski, Andrzej, Complexity of finding embeddings in a k-tree, SIAM Journal on Algebraic and Discrete Methods, 1987, 8 (2): 277–284, doi:10.1137/0608024.
Aspvall, Bengt; Proskurowski, Andrzej; Telle, Jan Arne, Memory requirements for table computations in partial k-tree algorithms, Algorithmica, 2000, 27 (3): 382–394, S2CID 9690525, doi:10.1007/s004530010025.
Berge, Claude, Some classes of perfect graphs, Graph Theory and Theoretical Physics, New York: Academic Press: 155–165, 1967.
Bienstock, Dan; Robertson, Neil; Seymour, Paul; Thomas, Robin, Quickly excluding a forest, Journal of Combinatorial Theory, Series B, 1991, 52 (2): 274–283, doi:10.1016/0095-8956(91)90068-U.
Björklund, Andreas; Husfeldt, Thore, Exact algorithms for exact satisfiability and number of perfect matchings, Algorithmica, 2008, 52 (2): 226–249, S2CID 37693881, doi:10.1007/s00453-007-9149-8.
Bodlaender, Hans L., A tourist guide through treewidth, Dassow, Jürgen; Kelemenová, Alisa (編), Developments in Theoretical Computer Science (Proc. 7th International Meeting of Young Computer Scientists, Smolenice, 16–20 November 1992), Topics in Computer Mathematics 6, Gordon and Breach: 1–20, 1994.
Bodlaender, Hans L. A tourist guide through treewidth. Acta Cybernetica. 1994a, 11: 1–2.
Bodlaender, Hans L., A linear-time algorithm for finding tree-decompositions of small treewidth, SIAM Journal on Computing, 1996, 25 (6): 1305–1317, doi:10.1137/S0097539793251219, hdl:1874/16670.
Bodlaender, Hans L., A partial k-arboretum of graphs with bounded treewidth, Theoretical Computer Science, 1998, 209 (1–2): 1–45, doi:10.1016/S0304-3975(97)00228-4.
Bodlaender, Hans L.; Fomin, Fedor V., Approximation of pathwidth of outerplanar graphs, Journal of Algorithms, 2002, 43 (2): 190–200, doi:10.1016/S0196-6774(02)00001-9.
Bodlaender, Hans L.; Gilbert, John R.; Hafsteinsson, Hjálmtýr; Kloks, Ton, Approximating treewidth, pathwidth, and minimum elimination tree height, Graph-Theoretic Concepts in Computer Science, Lecture Notes in Computer Science570: 1–12, 1992, ISBN 978-3-540-55121-8, doi:10.1007/3-540-55121-2_1, hdl:1874/17927.
Bodlaender, Hans L.; Kloks, Ton, Efficient and constructive algorithms for the pathwidth and treewidth of graphs, Journal of Algorithms, 1996, 21 (2): 358–402, doi:10.1006/jagm.1996.0049, hdl:1874/16538.
Bodlaender, Hans L.; Kloks, Ton; Kratsch, Dieter, Treewidth and pathwidth of permutation graphs, Proc. 20th International Colloquium on Automata, Languages and Programming (ICALP 1993), Lecture Notes in Computer Science 700, Springer-Verlag: 114–125, 1993, ISBN 978-3-540-56939-8, doi:10.1007/3-540-56939-1_66, hdl:1874/16657.
Bodlaender, Hans L.; Möhring, Rolf H., The pathwidth and treewidth of cographs, Proc. 2nd Scandinavian Workshop on Algorithm Theory, Lecture Notes in Computer Science 447, Springer-Verlag: 301–309, 1990, ISBN 978-3-540-52846-3, doi:10.1007/3-540-52846-6_99, hdl:1874/16625.
Cattell, Kevin; Dinneen, Michael J.; Fellows, Michael R., A simple linear-time algorithm for finding path-decompositions of small width, Information Processing Letters, 1996, 57 (4): 197–203, S2CID 2442557, arXiv:math/9410211, doi:10.1016/0020-0190(95)00190-5.
Diestel, Reinhard, Graph Minors I: a short proof of the path-width theorem, Combinatorics, Probability and Computing, 1995, 4 (1): 27–30, doi:10.1017/S0963548300001450.
Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Kawarabayashi, Ken-ichi, Algorithmic graph minor theory: decomposition, approximation, and coloring, Proc. 46th IEEE Symposium on Foundations of Computer Science (FOCS 2005): 637–646, 2005, ISBN 0-7695-2468-0, S2CID 13238254, doi:10.1109/SFCS.2005.14.
Downey, Rod G.; Fellows, Michael R., Parameterized Complexity, Springer-Verlag, 1999, ISBN 0-387-94883-X.
Dujmović, V.; Fellows, M.R.; Kitching, M.; Liotta, G.; McCartin, C.; Nishimura, N.; Ragde, P.; Rosamond, F.; Whitesides, S.; Wood, David R., On the parameterized complexity of layered graph drawing, Algorithmica, 2008, 52 (2): 267–292, S2CID 2298634, doi:10.1007/s00453-007-9151-1.
Dujmović, Vida; Morin, Pat; Wood, David R., Path-width and three-dimensional straight-line grid drawings of graphs(PDF), Proc. 10th International Symposium on Graph Drawing (GD 2002), Lecture Notes in Computer Science 2528, Springer-Verlag: 42–53, 2003 [2024-01-31], (原始內容存檔(PDF)於2012-03-04).
Ellis, J. A.; Sudborough, I. H.; Turner, J. S., Graph separation and search number, Proc. 1983 Allerton Conf. on Communication, Control, and Computing, 1983. As cited by Monien & Sudborough (1988).
Ellis, J. A.; Sudborough, I. H.; Turner, J. S., The vertex separation and search number of a tree, Information and Computation, 1994, 113 (1): 50–79, doi:10.1006/inco.1994.1064.
Feige, Uriel; Hajiaghayi, Mohammadtaghi; Lee, James R., Improved approximation algorithms for minimum-weight vertex separators, Proc. 37th ACM Symposium on Theory of Computing (STOC 2005): 563–572, 2005, ISBN 1581139608, S2CID 14097859, doi:10.1145/1060590.1060674.
Fellows, Michael R.; Langston, Michael A., On search decision and the efficiency of polynomial-time algorithms, Proc. 21st ACM Symposium on Theory of Computing: 501–512, 1989, ISBN 0897913078, S2CID 1854173, doi:10.1145/73007.73055.
Ferreira, Afonso G.; Song, Siang W., Achieving optimality for gate matrix layout and PLA folding: a graph theoretic approach, Proc. 1st Latin American Symposium on Theoretical Informatics (LATIN '92), Lecture Notes in Computer Science 583, Springer-Verlag: 139–153, 1992, ISBN 3-540-55284-7, doi:10.1007/BFb0023825, hdl:10068/43314.
Fomin, Fedor V.; Høie, Kjartan, Pathwidth of cubic graphs and exact algorithms, Information Processing Letters, 2006, 97 (5): 191–196, doi:10.1016/j.ipl.2005.10.012.
Fomin, Fedor V.; Kratsch, Dieter; Todinca, Ioan; Villanger, Yngve, Exact algorithms for treewidth and minimum fill-in, SIAM Journal on Computing, 2008, 38 (3): 1058–1079, doi:10.1137/050643350, hdl:1956/1151.
Fomin, Fedor V.; Thilikos, Dimitrios M., On self duality of pathwidth in polyhedral graph embeddings, Journal of Graph Theory, 2007, 55 (1): 42–54, doi:10.1002/jgt.20219.
Garbe, Renate, Tree-width and path-width of comparability graphs of interval orders, Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science 903, Springer-Verlag: 26–37, 1995, ISBN 978-3-540-59071-2, doi:10.1007/3-540-59071-4_35.
Golovach, P. A., The cutwidth of a graph and the vertex separation number of the line graph, Discrete Mathematics and Applications, 1993, 3 (5): 517–522, S2CID 120745961, doi:10.1515/dma.1993.3.5.517.
Gurski, Frank; Wanke, Egon, Line graphs of bounded clique-width, Discrete Mathematics, 2007, 307 (22): 2734–2754, doi:10.1016/j.disc.2007.01.020.
Gustedt, Jens, On the pathwidth of chordal graphs, Discrete Applied Mathematics, 1993, 45 (3): 233–248, doi:10.1016/0166-218X(93)90012-D.
Habib, Michel; Möhring, Rolf H., Treewidth of cocomparability graphs and a new order-theoretic parameter, Order, 1994, 11 (1): 47–60, S2CID 2648030, doi:10.1007/BF01462229.
Hliněny, Petr, Crossing-number critical graphs have bounded path-width, Journal of Combinatorial Theory, Series B, 2003, 88 (2): 347–367, doi:10.1016/S0095-8956(03)00037-6.
Kashiwabara, T.; Fujisawa, T., NP-completeness of the problem of finding a minimum-clique-number interval graph containing a given graph as a subgraph, Proc. International Symposium on Circuits and Systems: 657–660, 1979.
Kinnersley, Nancy G., The vertex separation number of a graph equals its path-width, Information Processing Letters, 1992, 42 (6): 345–350, doi:10.1016/0020-0190(92)90234-M.
Kinnersley, Nancy G.; Langston, Michael A., Obstruction set isolation for the gate matrix layout problem, Discrete Applied Mathematics, 1994, 54 (2–3): 169–213, doi:10.1016/0166-218X(94)90021-3.
Kloks, Ton; Bodlaender, Hans L., Approximating treewidth and pathwidth of some classes of perfect graphs, Proc. 3rd International Symposium on Algorithms and Computation (ISAAC'92), Lecture Notes in Computer Science 650, Springer-Verlag: 116–125, 1992, ISBN 978-3-540-56279-5, doi:10.1007/3-540-56279-6_64, hdl:1874/16672.
Kloks, T.; Bodlaender, H.; Müller, H.; Kratsch, D., Computing treewidth and minimum fill-in: all you need are the minimal separators, Proc. 1st European Symposium on Algorithms (ESA'93) (Lecture Notes in Computer Science)726, Springer-Verlag: 260–271, 1993, doi:10.1007/3-540-57273-2_61.
Kloks, Ton; Kratsch, Dieter; Müller, H., Dominoes, Proc. 20th International Workshop Graph-Theoretic Concepts in Computer Science (WG'94), Lecture Notes in Computer Science 903, Springer-Verlag: 106–120, 1995, ISBN 978-3-540-59071-2, doi:10.1007/3-540-59071-4_41.
Kneis, Joachim; Mölle, Daniel; Richter, Stefan; Rossmanith, Peter, Algorithms based on the treewidth of sparse graphs, Proc. 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2005), Lecture Notes in Computer Science 3787, Springer-Verlag: 385–396, 2005, ISBN 978-3-540-31000-6, doi:10.1007/11604686_34.
Lopez, Alexander D.; Law, Hung-Fai S., A dense gate matrix layout method for MOS VLSI, IEEE Transactions on Electron Devices, 1980, 27 (8): 1671–1675, Bibcode:1980ITED...27.1671L, S2CID 64469353, doi:10.1109/T-ED.1980.20086, Also in the joint issue, IEEE Journal of Solid-State Circuits15 (4): 736–740, 1980.
Möhring, Rolf H., Graph problems related to gate matrix layout and PLA folding, Tinhofer, G.; Mayr, E.; Noltemeier, H.; et al (編), Computational Graph Theory, Computing Supplementum 7, Springer-Verlag: 17–51, 1990, ISBN 3-211-82177-5.
Monien, B.; Sudborough, I. H., Min cut is NP-complete for edge weighted trees, Theoretical Computer Science, 1988, 58 (1–3): 209–229, doi:10.1016/0304-3975(88)90028-X.
Ohtsuki, Tatsuo; Mori, Hajimu; Kuh, Ernest S.; Kashiwabara, Toshinobu; Fujisawa, Toshio, One-dimensional logic gate assignment and interval graphs, IEEE Transactions on Circuits and Systems, 1979, 26 (9): 675–684, doi:10.1109/TCS.1979.1084695.
Peng, Sheng-Lung; Ho, Chin-Wen; Hsu, Tsan-sheng; Ko, Ming-Tat; Tang, Chuan Yi, A linear-time algorithm for constructing an optimal node-search strategy of a tree, Proc. 4th Int. Conf. Computing and Combinatorics (COCOON'98), Lecture Notes in Computer Science 1449, Springer-Verlag: 197–205, 1998[失效連結].
Proskurowski, Andrzej; Telle, Jan Arne, Classes of graphs with restricted interval models(PDF), Discrete Mathematics and Theoretical Computer Science, 1999, 3: 167–176 [2024-01-31], (原始內容存檔(PDF)於2024-01-31).
Robertson, Neil; Seymour, Paul, Graph minors. I. Excluding a forest, Journal of Combinatorial Theory, Series B, 1983, 35 (1): 39–61, doi:10.1016/0095-8956(83)90079-5.
Robertson, Neil; Seymour, Paul, Graph minors. XVI. Excluding a non-planar graph, Journal of Combinatorial Theory, Series B, 2003, 89 (1): 43–76, doi:10.1016/S0095-8956(03)00042-X.
Robertson, Neil; Seymour, Paul D., Graph Minors. XX. Wagner's conjecture, Journal of Combinatorial Theory, Series B, 2004, 92 (2): 325–357, doi:10.1016/j.jctb.2004.08.001.
Scheffler, Petra, A linear algorithm for the pathwidth of trees, Bodendiek, R.; Henn, R. (編), Topics in Combinatorics and Graph Theory, Physica-Verlag: 613–620, 1990.
Scheffler, Petra, Optimal embedding of a tree into an interval graph in linear time, Nešetřil, Jaroslav; Fiedler, Miroslav (編), Fourth Czechoslovakian Symposium on Combinatorics, Graphs and Complexity, Elsevier, 1992.
Skodinis, Konstantin, Computing optimal linear layouts of trees in linear time, Proc. 8th European Symposium on Algorithms (ESA 2000), Lecture Notes in Computer Science 1879, Springer-Verlag: 403–414, 2000, ISBN 978-3-540-41004-1, doi:10.1007/3-540-45253-2_37.
Skodinis, Konstantin, Construction of linear tree-layouts which are optimal with respect to vertex separation in linear time, Journal of Algorithms, 2003, 47 (1): 40–59, doi:10.1016/S0196-6774(02)00225-0.
Suchan, Karol; Todinca, Ioan, Pathwidth of circular-arc graphs, Proc. 33rd International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2007), Lecture Notes in Computer Science 4769, Springer-Verlag: 258–269, 2007, doi:10.1007/978-3-540-74839-7_25.
Takahashi, Atsushi; Ueno, Shuichi; Kajitani, Yoji, Minimal acyclic forbidden minors for the family of graphs with bounded path-width, Discrete Mathematics, 1994, 127 (1–3): 293–304, doi:10.1016/0012-365X(94)90092-2.
Wikiwand in your browser!
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.