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.