書目名稱Graph-Theoretic Concepts in Computer Science影響因子(影響力)學(xué)科排名
書目名稱Graph-Theoretic Concepts in Computer Science網(wǎng)絡(luò)公開度
書目名稱Graph-Theoretic Concepts in Computer Science網(wǎng)絡(luò)公開度學(xué)科排名
書目名稱Graph-Theoretic Concepts in Computer Science被引頻次
書目名稱Graph-Theoretic Concepts in Computer Science被引頻次學(xué)科排名
書目名稱Graph-Theoretic Concepts in Computer Science年度引用
書目名稱Graph-Theoretic Concepts in Computer Science年度引用學(xué)科排名
書目名稱Graph-Theoretic Concepts in Computer Science讀者反饋
書目名稱Graph-Theoretic Concepts in Computer Science讀者反饋學(xué)科排名
作者: Insul島 時(shí)間: 2025-3-21 22:08
Modernisierung der Berufsbildung in Europaubgraph in an edge-weighted graph . on . nodes. We present an .(..)-algorithm for the weak subgraph problem. If the maximal degree of . is bounded, the algorithm above can be modified to an .(..)-algorithm for the induced subgraph problem.作者: Recessive 時(shí)間: 2025-3-22 01:07 作者: apiary 時(shí)間: 2025-3-22 04:43
https://doi.org/10.1057/9781137393753er of other processors (.). A message-routing paradigm for such a multidestination communication has been formulated as finding a subgraph called an . (ODPT). We prove that the problem of finding an ODPT is NP-hard both for the .-cube graph as well as for a graph whose maximum degree is at most three.作者: Deceit 時(shí)間: 2025-3-22 09:02 作者: 胰臟 時(shí)間: 2025-3-22 16:09
Two polynomial problems in PLA folding,e-folding problems are known to be NP-hard. We define the compatibility graph of a PLA as the complement of its column-disjoint graph, and prove that both block-folding and variable-folding can be solved in polynomial time on PLA whose compatibility graph does not contain a claw or a (K. ? e) as induced subgraph.作者: 胰臟 時(shí)間: 2025-3-22 17:14 作者: 煩人 時(shí)間: 2025-3-22 23:13
Modernisierung des ?ffentlichen DienstesWe prove by a reduction from 3SAT that the INDUCED SUBGRAPH ISOMORPHISM problem remains NP-complete when restricted to cographs (P.-free graphs).作者: 含糊 時(shí)間: 2025-3-23 03:11 作者: ABYSS 時(shí)間: 2025-3-23 08:59
Induced subraph isomorphism for cographs is NP-complete,We prove by a reduction from 3SAT that the INDUCED SUBGRAPH ISOMORPHISM problem remains NP-complete when restricted to cographs (P.-free graphs).作者: Arb853 時(shí)間: 2025-3-23 12:18
Embeddings of treelike graphs into 2-dimensional meshes,In the following we present embeddings of complete binary trees, pyramids and X-trees into 2-dimensional meshes. The presented embeddings achieve . expansion with congestion 2 for trees and congestion 6 for X-trees, and constant expansion ≤3 with congestion 3 for pyramids. The dilations are shown to be near optimal.作者: 要求比…更好 時(shí)間: 2025-3-23 16:35 作者: Defiance 時(shí)間: 2025-3-23 21:34
Finding minimally weighted subgraphs,ubgraph in an edge-weighted graph . on . nodes. We present an .(..)-algorithm for the weak subgraph problem. If the maximal degree of . is bounded, the algorithm above can be modified to an .(..)-algorithm for the induced subgraph problem.作者: 使困惑 時(shí)間: 2025-3-24 01:59 作者: 作繭自縛 時(shí)間: 2025-3-24 04:21 作者: 多產(chǎn)魚 時(shí)間: 2025-3-24 07:57 作者: 滑動(dòng) 時(shí)間: 2025-3-24 13:54 作者: 不可知論 時(shí)間: 2025-3-24 17:45 作者: vector 時(shí)間: 2025-3-24 19:24
Vertex-disjoint trees and boundary single-layer routing, consists of a set of . interconnecting the terminals belonging to the same (multi-terminal) net. An algorithm, unifying and generalizing previous BSLR algorithms, to solve an arbitrary instance of BSLR, is presented. Problems involving slidable terminals (i.e., when terminals can slide within a cer作者: multiply 時(shí)間: 2025-3-25 01:14
Bounds on the quality of approximate solutions to the group Steiner problem, required vertices and Steiner vertices, GSP asks for a shortest connected subgraph, containing at least one vertex of each group. As the Steiner Problem is NP-hard, GSP is too, and we are interested in approximation algorithms. Efficient approximation algorithms have already been proposed, but noth作者: 強(qiáng)制性 時(shí)間: 2025-3-25 06:08 作者: stressors 時(shí)間: 2025-3-25 10:48 作者: A簡潔的 時(shí)間: 2025-3-25 13:35
Approximating the minimum net expansion: Near optimal solutions to circuit partitioning problems,h endpoints into two different sets divided by the number of nodes of the smaller set. We prove that a solution or a constant times optimal approximation to the optimization version of a multicommodity flow problem yields a logarithmic, to the number of nets, approximation of the minimum net expansi作者: textile 時(shí)間: 2025-3-25 17:54
On complexity of a message-routing strategy for multicomputer systems,er of other processors (.). A message-routing paradigm for such a multidestination communication has been formulated as finding a subgraph called an . (ODPT). We prove that the problem of finding an ODPT is NP-hard both for the .-cube graph as well as for a graph whose maximum degree is at most thre作者: Commemorate 時(shí)間: 2025-3-25 20:18
Diagnosis of t/s-diagnosable systems,d integer .. The .-diagnosis algorithm of [10], the .+1-diagnosis algorithm of [11] and the .-diagnosis algorithm of this paper complement the corresponding .-diagnosability algorithms of Sullivan [12]. It is shown in [17] that the basic approach of the .-diagnosis algorithm of this paper can be use作者: 按等級(jí) 時(shí)間: 2025-3-26 01:42 作者: 一加就噴出 時(shí)間: 2025-3-26 07:06
Remarks on some concurrency measures,, concurrency measures proposed by Charron-Bost [1989] and Fidge [1989]) in concurrency theory with old and new results developped in computational order theory (interval orders, lattice of maximal antichains, minimax antichains). We hope that this approach will be fruitful in both domains, for exam作者: optic-nerve 時(shí)間: 2025-3-26 12:14
https://doi.org/10.1007/978-3-322-93306-5 coloring and maximal independent set in trees and bounded degree graphs; 7-colorability, maximal independent set and maximal matching in planar graphs; maximum independent set, maximum matching and Hamiltonian path on rectangular grid graphs. Our techniques are based on the . problem: given . lists作者: Carcinogenesis 時(shí)間: 2025-3-26 14:34 作者: mercenary 時(shí)間: 2025-3-26 20:26
Modernisierung der Kommunalpolitik .) with a color, taken from a given set ., such that never two adjacent vertices are colored with the same color. In one variant, the first player which is unable to move, loses the game. In another variant, player 1 wins the game if and only if the game ends with all vertices colored. We show that作者: 枯燥 時(shí)間: 2025-3-26 23:54 作者: 表皮 時(shí)間: 2025-3-27 02:00
Georg Müller-Christ,Michael Hülsmanntiplication are recognition of transitive graphs, computing the transitive closure of a directed acyclic graph, and finding the neighborhood containment matrix of a graph. In this paper, we show how to avoid using matrix multiplication for these problems on special classes of graphs. This leads to e作者: 疏遠(yuǎn)天際 時(shí)間: 2025-3-27 07:11
Modernisierung oder überfremdung?igraph (DAG). The main results in this paper are (n=|V|) :.(1) An O(n* log(n)) approximation algorithm is developed for the minimum-fas-problem on planar digraphs with a worst-case-ratio of 2. In the case of a planar digraph with all embeddings in the plane having at most one clockwise/anticlockwise作者: 思考才皺眉 時(shí)間: 2025-3-27 10:19 作者: Banquet 時(shí)間: 2025-3-27 14:59
https://doi.org/10.1007/978-3-642-59152-5 consists of a set of . interconnecting the terminals belonging to the same (multi-terminal) net. An algorithm, unifying and generalizing previous BSLR algorithms, to solve an arbitrary instance of BSLR, is presented. Problems involving slidable terminals (i.e., when terminals can slide within a cer作者: 無孔 時(shí)間: 2025-3-27 21:30
https://doi.org/10.1007/978-3-476-04340-5 required vertices and Steiner vertices, GSP asks for a shortest connected subgraph, containing at least one vertex of each group. As the Steiner Problem is NP-hard, GSP is too, and we are interested in approximation algorithms. Efficient approximation algorithms have already been proposed, but noth作者: 說不出 時(shí)間: 2025-3-27 23:35 作者: 誓言 時(shí)間: 2025-3-28 04:18
https://doi.org/10.1007/978-3-322-88722-1e. the problem of embedding a graph into a grid of minimum area is NP-hard, even for connected (but not necessarily planar) graphs..VLSI circuits (or large parts of them) are typically modelled by . graphs, but Kramer and van Leeuwen used a family of non-planar graphs for their reduction and they po作者: 帳單 時(shí)間: 2025-3-28 06:38 作者: 單挑 時(shí)間: 2025-3-28 12:55 作者: Bronchial-Tubes 時(shí)間: 2025-3-28 16:33 作者: Irremediable 時(shí)間: 2025-3-28 19:48 作者: 無辜 時(shí)間: 2025-3-28 23:18 作者: Cantankerous 時(shí)間: 2025-3-29 05:15
Modernisierung der Kommunalpolitikems are solvable in .(. + .), and . time, respectively, if |.| = 2. We also give polynomial time algorithms for the problems with certain restrictions on the graphs and orderings of the vertices. We give some partial results for the versions, where no order for coloring the vertices is specified.作者: 舊病復(fù)發(fā) 時(shí)間: 2025-3-29 09:44
https://doi.org/10.1007/978-3-663-01679-3ctually finds a path . described above if . and . satisfy four conditions; this theorem implies some assertions of [3]. Two further results deal with the possibility of replacing . and . by new decision functions . and . (resp.) with some . properties.作者: gain631 時(shí)間: 2025-3-29 12:05
On the complexity of some coloring games,ems are solvable in .(. + .), and . time, respectively, if |.| = 2. We also give polynomial time algorithms for the problems with certain restrictions on the graphs and orderings of the vertices. We give some partial results for the versions, where no order for coloring the vertices is specified.作者: myopia 時(shí)間: 2025-3-29 18:06 作者: 內(nèi)部 時(shí)間: 2025-3-29 20:24 作者: Outshine 時(shí)間: 2025-3-30 02:52 作者: 過分自信 時(shí)間: 2025-3-30 07:15 作者: 不發(fā)音 時(shí)間: 2025-3-30 11:56
Remarks on some concurrency measures,der theory (interval orders, lattice of maximal antichains, minimax antichains). We hope that this approach will be fruitful in both domains, for example we discuss some new measures and their associated computational complexity, that can be of some interest.作者: 引導(dǎo) 時(shí)間: 2025-3-30 12:57
https://doi.org/10.1007/978-3-322-93306-5RAM. For planar graphs they need .(log..) time and ./log.. processors on an EREW PRAM using linear space. For the case of rectangular grid graphs they need .(log .) time with ./log . processors on a CRCW PRAM, or on an EREW PRAM (if the embedding is given).作者: 有雜色 時(shí)間: 2025-3-30 17:14
https://doi.org/10.1007/978-3-531-92496-0lutions for a variety of partitioning and partitioning related problems on hypergraphs including bipartitioning, multiway partitioning and nonplanar net deletion. For several of the problems the solutions are within a polylogarithmic factor to the optimal solution.作者: TIA742 時(shí)間: 2025-3-31 00:07 作者: 暫時(shí)過來 時(shí)間: 2025-3-31 01:06 作者: HAIRY 時(shí)間: 2025-3-31 07:43
https://doi.org/10.1007/978-3-642-59152-5tain range on the boundary) and permutable terminals (i.e., when positions of some terminals [going to the same gate] can be interchanged) are optimally solved. The proposed algorithm runs in . (.) time, where . is the number of edges in the input graph. The result is extended to handle gridless routing environments.作者: 扔掉掐死你 時(shí)間: 2025-3-31 11:13 作者: 上釉彩 時(shí)間: 2025-3-31 17:13 作者: 異端邪說下 時(shí)間: 2025-3-31 17:51 作者: 無意 時(shí)間: 2025-4-1 00:14
Diagnosis of t/s-diagnosable systems,d to design a diagnosis algorithm for a sequentially .-diagnosable system which has complexity .(.. +..) where m and n are the number of edges and vertices, respectively, of the test interconnection graph.作者: 親屬 時(shí)間: 2025-4-1 04:19 作者: 法律 時(shí)間: 2025-4-1 06:50
Georg Müller-Christ,Michael Hülsmannnt matrix of a graph. In this paper, we show how to avoid using matrix multiplication for these problems on special classes of graphs. This leads to efficient algorithms for recognizing chordal comparability graphs and trapezoid graphs, computing the transitive closure of two dimensional partial orders, and a number of other problems.作者: 我怕被刺穿 時(shí)間: 2025-4-1 14:00
https://doi.org/10.1007/978-3-322-93225-9s for deciding whether an .-vertex graph . is a binary Hamming graph, and for computing a binary addressing scheme for . provided its existence. This is not far from being optimal since the addressing scheme may require .(..) space.
