書目名稱Graph-Theoretic Concepts in Computer Science影響因子(影響力)學科排名
書目名稱Graph-Theoretic Concepts in Computer Science網(wǎng)絡(luò)公開度
書目名稱Graph-Theoretic Concepts in Computer Science網(wǎng)絡(luò)公開度學科排名
書目名稱Graph-Theoretic Concepts in Computer Science被引頻次
書目名稱Graph-Theoretic Concepts in Computer Science被引頻次學科排名
書目名稱Graph-Theoretic Concepts in Computer Science年度引用
書目名稱Graph-Theoretic Concepts in Computer Science年度引用學科排名
書目名稱Graph-Theoretic Concepts in Computer Science讀者反饋
書目名稱Graph-Theoretic Concepts in Computer Science讀者反饋學科排名
作者: jocular 時間: 2025-3-21 23:00
,Extension Complexity of Stable Set Polytopes of?Bipartite Graphs, bound, we show that . is ., which is an improvement when . has quadratically many edges. For the lower bound, we prove that . is . when . is the incidence graph of a finite projective plane. We also provide examples of 3-regular bipartite graphs . such that the edge vs stable set matrix of . has a fooling set of size |.(.)|.作者: 不透氣 時間: 2025-3-22 01:28 作者: 表示向前 時間: 2025-3-22 05:29 作者: occult 時間: 2025-3-22 11:33
https://doi.org/10.1007/978-1-4471-0399-8rize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.作者: 飛鏢 時間: 2025-3-22 15:59
Hierarchical Partial Planarity,grees of importance. We give a polynomial-time testing algorithm when the graph induced by the two most important sets of edges is biconnected. We also discuss interesting relationships with other constrained-planarity problems.作者: 飛鏢 時間: 2025-3-22 17:38
Intersection Graphs of Rays and Grounded Segments,rize the complexity of the recognition problems for the classes of outer segment, grounded segment, and ray intersection graphs. We prove that these recognition problems are complete for the existential theory of the reals. This holds even if a 1-string realization is given as additional input.作者: tolerance 時間: 2025-3-22 22:47
https://doi.org/10.1007/978-3-030-92735-6 can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings.作者: foodstuff 時間: 2025-3-23 04:50
https://doi.org/10.1007/978-3-642-80530-1he two stubborn cases, namely for the case . by proving that the class of .-free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of 3-partite graphs. We also use this technique to completely determine which classes of .-free graphs are well-quasi-ordered.作者: 極肥胖 時間: 2025-3-23 09:21 作者: 淺灘 時間: 2025-3-23 10:21
,Uniquely Restricted Matchings and?Edge?Colorings, can be partitioned. We provide tight upper bounds in terms of the maximum degree and characterize all extremal graphs. Our constructive proofs yield efficient algorithms to determine the corresponding edge colorings.作者: 白楊魚 時間: 2025-3-23 15:38
Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes,he two stubborn cases, namely for the case . by proving that the class of .-free graphs has bounded clique-width and is well-quasi-ordered. Our technique is based on a special decomposition of 3-partite graphs. We also use this technique to completely determine which classes of .-free graphs are well-quasi-ordered.作者: Fallibility 時間: 2025-3-23 19:17 作者: Meander 時間: 2025-3-24 01:04 作者: milligram 時間: 2025-3-24 04:10 作者: 易怒 時間: 2025-3-24 06:51
https://doi.org/10.1007/978-3-319-71416-5direct consequence of the well-known formula for the number of labeled .-trees, while the lower bound is obtained from an explicit construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most?..作者: 容易做 時間: 2025-3-24 14:08 作者: intention 時間: 2025-3-24 17:46 作者: FLIP 時間: 2025-3-24 19:53 作者: Nmda-Receptor 時間: 2025-3-24 23:43
Modern Methods in Analytical Morphologyfor recognizing .-graphs. For the dominating set problem (parameterized by the size of .), we give .- and .-time algorithms on .-graphs and .-graphs, respectively. Our dominating set algorithm for .-graphs also provides .-time algorithms for the independent set and independent dominating set problems on .-graphs.作者: packet 時間: 2025-3-25 04:02
On Bubble Generators in Directed Graphs,be useful in practice since some pertinent information about all the bubbles can be more conveniently extracted from this compact set. Furthermore, we provide a polynomial-time algorithm to decompose any bubble of a graph into the bubbles of such a generator in a tree-like fashion.作者: 虛構(gòu)的東西 時間: 2025-3-25 09:58
Defective Coloring on Classes of Perfect Graphs,result by showing that . is in P for cographs if either . or . is fixed; that it is in P for trivially perfect graphs; and that it admits a sub-exponential time algorithm for cographs when both . and . are unbounded.作者: 加劇 時間: 2025-3-25 13:57 作者: 聯(lián)想記憶 時間: 2025-3-25 16:10 作者: Middle-Ear 時間: 2025-3-25 20:07
Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions, many disciplines. It has the wonderful property, that, conditioned on being simple, it is a uniform random graph with the prescribed degrees. This is a beautiful example of a general technique called the . that was pioneered by Erd?s. It allows us to count rather precisely how many graphs there are作者: 極為憤怒 時間: 2025-3-26 03:45 作者: 煩躁的女人 時間: 2025-3-26 05:21 作者: forestry 時間: 2025-3-26 11:07
Hierarchical Partial Planarity,ecently they appeared in the scene, in a streaming setting. The goal is to construct layouts in which the readability of an edge is proportional to its importance, that is, more important edges have fewer crossings. We formalize this problem and study the case in which there exist three different de作者: 配偶 時間: 2025-3-26 15:54 作者: 弄臟 時間: 2025-3-26 19:17 作者: NADIR 時間: 2025-3-27 00:38
On the Number of Labeled Graphs of Bounded Treewidth, and some explicit absolute constant .. Disregarding lower-order terms, the gap between the lower and upper bound is of order .. The upper bound is a direct consequence of the well-known formula for the number of labeled .-trees, while the lower bound is obtained from an explicit construction. It fo作者: Bucket 時間: 2025-3-27 03:25
,Uniquely Restricted Matchings and?Edge?Colorings,d studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algori作者: Conscientious 時間: 2025-3-27 07:47
Defective Coloring on Classes of Perfect Graphs,e show that this natural generalization of . is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters . is set to the smallest possible fixed value that does not trivialize the problem (. or .). Together with a simp作者: 環(huán)形 時間: 2025-3-27 12:05 作者: 極力證明 時間: 2025-3-27 17:34
Computing Maximum Cliques in ,-EPG Graphs, graphs where the path on the grid associated to each vertex has at most . bends. Epstein et al. showed in 2013 that computing a maximum clique in .-EPG graphs is polynomial. As remarked in?[Heldt et al. 2014], when the number of bends is at least 4, the class contains 2-interval graphs for which co作者: ECG769 時間: 2025-3-27 20:27
Intersection Graphs of Rays and Grounded Segments,In particular, we show that:.The first result answers an open problem posed by Cabello and Jej?i?. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characte作者: notification 時間: 2025-3-27 23:00
On ,-Topological Intersection Graphs,ally generalize many important classes of graphs, e.g., interval graphs and circular-arc graphs. Our paper is the first study of the recognition and dominating set problems of this large collection of intersection classes of graphs..We negatively answer the question of Biró, Hujter, and Tuza who ask作者: 得罪 時間: 2025-3-28 04:46 作者: 低位的人或事 時間: 2025-3-28 09:13 作者: 中國紀念碑 時間: 2025-3-28 12:54 作者: 難管 時間: 2025-3-28 15:34 作者: 無法取消 時間: 2025-3-28 20:40
,Finding Cut-Vertices in the Square Roots of?a?Graph, . asks for the recognition of the squares of graphs in .. In this paper, we answer positively to an open question of [Golovach et al. IWOCA 2016] by showing that the squares of . can be recognized in polynomial time. Our proof is based on new relationships between the decomposition of a graph by cu作者: precede 時間: 2025-3-29 00:02 作者: 虛度 時間: 2025-3-29 03:17
Modern Management of Cancer of the Rectum many disciplines. It has the wonderful property, that, conditioned on being simple, it is a uniform random graph with the prescribed degrees. This is a beautiful example of a general technique called the . that was pioneered by Erd?s. It allows us to count rather precisely how many graphs there are作者: 起波瀾 時間: 2025-3-29 08:38
https://doi.org/10.1007/978-94-015-0772-1tive splicing events in a reference-free context can be done by enumerating all bubbles in a de Bruijn graph built from RNA-seq reads [.]. However, listing and analysing all bubbles in a given graph is usually unfeasible in practice, due to the exponential number of bubbles present in real data grap作者: 可互換 時間: 2025-3-29 12:57 作者: G-spot 時間: 2025-3-29 18:02
Modern Marketing Communicationsecently they appeared in the scene, in a streaming setting. The goal is to construct layouts in which the readability of an edge is proportional to its importance, that is, more important edges have fewer crossings. We formalize this problem and study the case in which there exist three different de作者: 解凍 時間: 2025-3-29 20:47 作者: 詳細目錄 時間: 2025-3-30 00:14
https://doi.org/10.1007/978-94-011-5628-8, and no isolated vertices. Let . be the convex hull of the stable sets of .. It is easy to see that .. We improve both of these bounds. For the upper bound, we show that . is ., which is an improvement when . has quadratically many edges. For the lower bound, we prove that . is . when . is the inci作者: nonsensical 時間: 2025-3-30 04:11 作者: 油氈 時間: 2025-3-30 10:45
https://doi.org/10.1007/978-3-030-92735-6d studied in a number of articles. Our contribution is twofold. We provide approximation algorithms for computing a uniquely restricted matching of maximum size in some bipartite graphs. In particular, we achieve a ratio of 5/9 for subcubic bipartite graphs, improving over a 1/2-approximation algori作者: 喧鬧 時間: 2025-3-30 15:34
Ton J. Cleophas,Aeilko H. Zwindermane show that this natural generalization of . is much harder on several basic graph classes. In particular, we show that it is NP-hard on split graphs, even when one of the two parameters . is set to the smallest possible fixed value that does not trivialize the problem (. or .). Together with a simp作者: 粗糙 時間: 2025-3-30 17:04
Robert Hawkes,Ingrid Mann,Peter Brown graph as long as the set of tokens still defines an independent set of .. Given two independent sets . and ., the . problem consists in deciding whether there exists a sequence of independent sets which transforms . into . so that every pair of consecutive independent sets of the sequence can be ob作者: Magnificent 時間: 2025-3-30 20:51
https://doi.org/10.1007/978-94-007-3024-3 graphs where the path on the grid associated to each vertex has at most . bends. Epstein et al. showed in 2013 that computing a maximum clique in .-EPG graphs is polynomial. As remarked in?[Heldt et al. 2014], when the number of bends is at least 4, the class contains 2-interval graphs for which co作者: entrance 時間: 2025-3-31 02:58
https://doi.org/10.1007/978-1-4471-0399-8In particular, we show that:.The first result answers an open problem posed by Cabello and Jej?i?. The third result confirms a conjecture by Cabello. We thereby completely elucidate the remaining open questions on the containment relations between these classes of segment graphs. We further characte作者: 阻塞 時間: 2025-3-31 05:26 作者: LITHE 時間: 2025-3-31 11:33 作者: absolve 時間: 2025-3-31 16:44
Kent K. Stewart,John R. Whitakervertices, for fixed .. We propose an algorithm that, given a 3-colorable graph without an induced path on . vertices, computes a coloring with . many colors. If the input graph is triangle-free, we only need . many colors. The running time of our algorithm is . if the input graph has . vertices and 作者: BOLT 時間: 2025-3-31 17:34
https://doi.org/10.1007/978-1-4684-1830-9ne to another. An instance of the problem consists of a capacitated directed network, in which vertices express their preferences over their incident edges. A network flow is stable if there is no group of vertices that all could benefit from rerouting the flow along a walk..Fleiner?[.] established 作者: Congeal 時間: 2025-4-1 00:56 作者: 拒絕 時間: 2025-4-1 04:15 作者: 法律 時間: 2025-4-1 09:00
https://doi.org/10.1007/978-3-642-48141-3while using at most?.?edges more than once. We show that?MSE can be decided on bounded (i.e. finite) grids in linear time when both dimensions are either small or large compared to the number?. of paths. On the contrary, we show that?MSE remains .-hard on subgraphs of bounded grids..Finally, we stud作者: 不易燃 時間: 2025-4-1 12:24
Graph-Theoretic Concepts in Computer Science978-3-319-68705-6Series ISSN 0302-9743 Series E-ISSN 1611-3349 作者: 籠子 時間: 2025-4-1 15:08
Modern Methods in Mathematical Physicstern graphs” can be embedded into a given graph . (that is, is isomorphic to a subgraph of .) is fixed-parameter tractable if . is a class of graphs of bounded tree width and .-complete otherwise..Towards this conjecture, we prove that the embedding problem is .-complete if . is the class of all grids or the class of all walls.
