Info
- Utilizzare la checkbox di selezione a fianco di ciascun documento per attivare le funzionalità di stampa, invio email, download nei formati disponibili del (i) record.
Algorithms – ESA 2013 [[electronic resource] ] : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano
| Algorithms – ESA 2013 [[electronic resource] ] : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano |
| Edizione | [1st ed. 2013.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
| Descrizione fisica | 1 online resource (XVIII, 829 p. 134 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer networks Computer science—Mathematics Discrete mathematics Computer graphics Numerical analysis Artificial intelligence—Data processing Computer Communication Networks Discrete Mathematics in Computer Science Computer Graphics Numerical Analysis Data Science |
| ISBN | 3-642-40450-2 |
| Formato | Materiale a stampa  |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Algorithm engineering -- Algorithmic aspects of networks -- Algorithmic game theory -- Approximation algorithms -- Computational biology -- Computational finance -- Computational geometry -- Combinatorial optimization -- Data compression -- Data structures -- Databases and information retrieval -- Distributed and parallel computing -- Graph algorithms -- Hierarchical memories -- Heuristics and meta-heuristics -- Mathematical programming -- Mobile computing -- On-line algorithms -- Parameterized complexity -- Pattern matching -- Quantum computing -- Randomized algorithms -- Scheduling and resource allocation problems -- Streaming algorithms. |
| Record Nr. | UNISA-996465943803316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Algorithms – ESA 2013 : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano
| Algorithms – ESA 2013 : 21st Annual European Symposium, Sophia Antipolis, France, September 2-4, 2013. Proceedings / / edited by Hans L. Bodlaender, Giuseppe F. Italiano |
| Edizione | [1st ed. 2013.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 |
| Descrizione fisica | 1 online resource (XVIII, 829 p. 134 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer networks Computer science—Mathematics Discrete mathematics Computer graphics Numerical analysis Artificial intelligence—Data processing Computer Communication Networks Discrete Mathematics in Computer Science Computer Graphics Numerical Analysis Data Science |
| ISBN | 3-642-40450-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Algorithm engineering -- Algorithmic aspects of networks -- Algorithmic game theory -- Approximation algorithms -- Computational biology -- Computational finance -- Computational geometry -- Combinatorial optimization -- Data compression -- Data structures -- Databases and information retrieval -- Distributed and parallel computing -- Graph algorithms -- Hierarchical memories -- Heuristics and meta-heuristics -- Mathematical programming -- Mobile computing -- On-line algorithms -- Parameterized complexity -- Pattern matching -- Quantum computing -- Randomized algorithms -- Scheduling and resource allocation problems -- Streaming algorithms. |
| Record Nr. | UNINA-9910485025703321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2013 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger
| Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XIII, 440 p. 87 illus.) |
| Disciplina | 511.5 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science—Mathematics
Discrete mathematics Algorithms Artificial intelligence—Data processing Computer graphics Geometry Discrete Mathematics in Computer Science Data Science Computer Graphics |
| ISBN | 3-319-68705-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions -- 1 Complex Networks and Random Graphs: A Motivation -- 2 Random Graphs and Real-World Networks -- 3 Random Graph Models as Null Models -- 3.1 Null Model 1: Uniform Random Graph -- 3.2 Null Model 2: Erdős-Rényi Random Graph with Fixed Number of Edges -- 3.3 Null Model 3: Fixing All Degrees and the Configuration Model -- 3.4 Small-World Properties of the Configuration Model -- 4 Extensions: Other Models -- References -- On Bubble Generators in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Bubble Generator -- 4 A Polynomial-Time Algorithm for Decomposing a Bubble -- 5 Conclusions and Open Problems -- References -- Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard -- 1 Introduction -- 2 Preliminaries -- 3 W[1]-HardNess of SumCSP -- 4 W[1]-HardNess of CNC -- References -- Hierarchical Partial Planarity -- 1 Introduction -- 2 Preliminaries -- 3 Relationships to Other Planarity Problems -- 4 Biconnected Facial-Constrained Core Planarity -- 4.1 High-Level Description of the Algorithm -- 4.2 Detailed Description of the Algorithm -- 5 Open Problems -- References -- On the Relationship Between k-Planar and k-Quasi-Planar Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Edge Rerouting Operations and Proof Strategy -- 4 Removing Tangled (k+1)-Crossings -- 5 Removing Untangled (k+1)-Crossings -- 5.1 Obtaining (k+1)-Quasi-Planarity -- 5.2 Obtaining Simplicity -- 6 Conclusions and Open Problems -- References -- Extension Complexity of Stable Set Polytopes of Bipartite Graphs -- 1 Introduction -- 2 Rectangle Covers and Fooling Sets -- 3 An Improved Upper Bound -- 4 An Improved Lower Bound -- 5 A Small Rectangle Cover of the Special Entries -- References.
On the Number of Labeled Graphs of Bounded Treewidth -- 1 Introduction -- 2 The Construction -- 2.1 Notation and Definitions -- 2.2 Description of the Construction -- 2.3 Bounding the Treewidth -- 3 Proof of the Main Result -- 3.1 Number of Constructible Triples (, F, N) -- 3.2 Bounding the Number of Duplicates -- 3.3 Choosing the Parameter s -- 4 Concluding Remarks and Further Research -- References -- Uniquely Restricted Matchings and Edge Colorings -- 1 Introduction -- 2 Approximation Algorithms for Bipartite Graphs -- 3 Upper Bounds on ur'(G) -- 4 Concluding Remarks -- References -- Defective Coloring on Classes of Perfect Graphs -- 1 Introduction -- 2 Preliminaries and Definitions -- 3 NP-Hardness on Cographs -- 4 Polynomial Time Algorithm on Trivially Perfect Graphs -- 5 Algorithms on Cographs -- 5.1 Algorithm for Small Deficiency -- 5.2 Algorithm for Few Colors -- 5.3 Sub-Exponential Time Algorithm -- 6 Split and Chordal Graphs -- 6.1 Hardness for Bounded Deficiency -- 6.2 Hardness for Bounded Number of Colors -- 6.3 A Dynamic Programming Algorithm -- 7 Conclusions -- References -- Token Sliding on Chordal Graphs -- 1 Introduction -- 2 Hardness Results -- 2.1 Split Graphs -- 2.2 Bipartite Graphs -- 3 Interval Graphs -- 3.1 Basic Facts on Independent Sets in Interval Graphs -- 3.2 Reachability -- 3.3 Connectivity -- References -- Computing Maximum Cliques in B2-EPG Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Typed Intervals and Projection Graphs -- 3.1 Typed Intervals -- 3.2 Projection Graphs -- 4 Maximum Clique in B2-EPG Graphs -- 4.1 Graphs with Z-Vertices -- 4.2 General B2-EPG Graphs -- 5 Colorings and -boundedness -- References -- Intersection Graphs of Rays and Grounded Segments -- 1 Introduction -- 2 Preliminaries -- 3 Cycle Lemma -- 4 Stretchability -- 5 Rays and Segments -- References -- On H-Topological Intersection Graphs. 1 Introduction -- 2 Recognition of T-Graphs -- 3 Recognition Hardness -- 4 Dominating Set -- References -- The Hardness of Embedding Grids and Walls -- 1 Introduction -- 2 Preliminaries -- 2.1 From Homomorphism to Colored Embedding -- 3 Frames and Skeletons -- 4 Conclusions -- References -- Approximately Coloring Graphs Without Long Induced Paths -- 1 Introduction -- 2 Algorithm -- 3 Hardness Result -- 4 Conclusion -- References -- New and Simple Algorithms for Stable Flow Problems -- 1 Introduction -- 2 Preliminaries -- 3 A Polynomial-Time Augmenting Path Algorithm for Stable Flows -- 4 Stable Flows with Restricted Intervals -- 4.1 Forced Edges -- 4.2 Forbidden Edges -- 5 Stable Multicommodity Flows -- 5.1 Problem Simplification -- 5.2 Integral Multicommodity Stable Flows -- References -- Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Partitioning 3-Partite Graphs -- 4 Applications of Our Technique -- References -- Finding Cut-Vertices in the Square Roots of a Graph -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Squares and Powers of Graphs -- 2.2 Graph Decompositions -- 3 Basic Properties of the Atoms in a Square -- 4 Computation of the Cut-Vertices from the Square -- 4.1 Recognition of the Essential Cut-Vertices -- 4.2 Sufficient Conditions for Non Essential Cut-Vertices -- 5 Reconstructing the Block-Cut Tree of a Square Root -- 6 Application to Trees of Cycle-Powers -- 7 Conclusion -- References -- The Minimum Shared Edges Problem on Grid-Like Graphs -- 1 Introduction -- 2 Preliminaries -- 3 On Bounded and Holey Grids -- 3.1 Bounded Grids -- 3.2 Holey Grids -- 3.3 Manhattan-Like Acyclic Digraphs -- 4 The Nonexistence of Polynomial Kernels -- 5 Conclusion -- References -- Linearly -Bounding (P6,C4)-Free Graphs -- 1 Introduction. 2 Preliminaries -- 3 The Structure of (P6,C4)-Free Atoms -- 4 -Bounding (P6,C4)-Free Graphs -- 5 A 3/2-Approximation Algorithm -- References -- Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2 -- 1 Introduction -- 2 Preliminaries -- 3 Outerplanar Roots -- 3.1 Structural Lemmas -- 3.2 The Algorithm -- 4 Roots of Pathwidth at Most Two -- 5 Conclusions -- References -- Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Enumeration of Maximal Irredundant Sets for Chordal Graphs -- 4 Enumeration of Maximal Irredundant Sets for Interval Graphs -- 5 Conclusions -- References -- The Minimum Conflict-Free Row Split Problem Revisited -- 1 Introduction -- 2 Formulations in Terms of Branchings in Directed Acyclic Graphs -- 3 A Strengthening of Dilworth's Theorem and Its Connection to the MCRS Problem -- 3.1 A Min-Max Relation Strengthening Dilworth's Theorem -- 3.2 Connection with the MCRS Problem -- 4 (In)approximability Issues -- 4.1 Hardness Results -- 4.2 2-Approximating and via Laminar Set Families -- 4.3 Two Approximation Algorithms for Computing and -- 5 Conclusion -- References -- Drawing Planar Graphs with Few Geometric Primitives -- 1 Introduction -- 2 Trees with Segments on the Grid -- 3 Planar 3-Trees with Few Segments on the Grid -- 4 Maximal Outerplanar Graphs with Segments on the Grid -- 5 Triangulations and Planar Graphs with Circular Arcs -- References -- Mixed Dominating Set: A Parameterized Perspective -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for MDS Parameterized by the Solution Size -- 4 Outline of Algorithm for MDS Parameterized by Treewidth -- 5 Lower Bounds -- 6 Conclusion -- References -- Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity -- 1 Introduction -- 1.1 Related Work. 1.2 Our Contribution -- 2 Preliminaries -- 2.1 MSO and Its Extensions -- 2.2 Treewidth and Neighborhood Diversity -- 3 Graphs of Bounded Neighborhood Diversity -- 4 XP Algorithm for MSOGL on Bounded Treewidth -- 4.1 CSP, MSO and Treewidth -- 4.2 CSP Instance Construction -- 5 Conclusions -- References -- Extending Partial Representations of Trapezoid Graphs -- 1 Introduction -- 2 Modular Decomposition and Transitive Orientations -- 3 Trapezoid Models -- 4 Extending Partial Representations of Trapezoid Posets -- 5 Extending Partial Representations of Trapezoid Graphs -- References -- On Low Rank-Width Colorings -- 1 Introduction and Main Results -- 2 Preliminaries -- 3 Powers of Sparse Graphs -- 4 Other Positive Results -- 5 Negative Results -- 6 Erdős-Hajnal property and -boundedness -- 7 Conclusions -- References -- On Strongly Chordal Graphs That Are Not Leaf Powers -- 1 Introduction -- 2 Preliminary Notions -- 3 Alternating Cycles and Quartets in Leaf Powers -- 4 Strongly Chordal Graphs That Are Not Leaf Powers -- 5 Hardness of Finding rq in Chordal Graphs -- 6 Conclusion -- References -- New Results on Weighted Independent Domination -- 1 Introduction -- 2 Preliminaries -- 2.1 Modular Decomposition -- 2.2 Antineighborhood Decomposition -- 3 WID in (P5,P5)-Free Graphs -- 3.1 Decomposition Scheme -- 3.2 Application to (P5,P5)-Free Graphs -- 4 WID in (P5, P3+P2)-Free Graphs -- 5 Concluding Remarks and Open Problems -- References -- The Parameterized Complexity of the Equidomination Problem -- 1 Introduction -- 2 Twin Relation -- 3 Properties of Twin Classes Regarding Equidomination -- 4 An XP Algorithm for the k-EQUIDOMINATION Problem -- 5 Reduction Rules -- 6 Main Results -- 7 Hereditarily Equidominating Graphs -- 8 Conclusion and Outlook -- References -- Homothetic Triangle Contact Representations -- 1 Introduction -- 2 Schnyder Woods. 3 The System of Linear Equations. |
| Record Nr. | UNISA-996466470603316 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger
| Graph-Theoretic Concepts in Computer Science : 43rd International Workshop, WG 2017, Eindhoven, The Netherlands, June 21-23, 2017, Revised Selected Papers / / edited by Hans L. Bodlaender, Gerhard J. Woeginger |
| Edizione | [1st ed. 2017.] |
| Pubbl/distr/stampa | Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 |
| Descrizione fisica | 1 online resource (XIII, 440 p. 87 illus.) |
| Disciplina | 511.5 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Computer science—Mathematics
Discrete mathematics Algorithms Artificial intelligence—Data processing Computer graphics Geometry Discrete Mathematics in Computer Science Data Science Computer Graphics |
| ISBN | 3-319-68705-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto |
Intro -- Preface -- Organization -- Contents -- Counting Graphs and Null Models of Complex Networks: Configuration Model and Extensions -- 1 Complex Networks and Random Graphs: A Motivation -- 2 Random Graphs and Real-World Networks -- 3 Random Graph Models as Null Models -- 3.1 Null Model 1: Uniform Random Graph -- 3.2 Null Model 2: Erdős-Rényi Random Graph with Fixed Number of Edges -- 3.3 Null Model 3: Fixing All Degrees and the Configuration Model -- 3.4 Small-World Properties of the Configuration Model -- 4 Extensions: Other Models -- References -- On Bubble Generators in Directed Graphs -- 1 Introduction -- 2 Preliminaries -- 3 The Bubble Generator -- 4 A Polynomial-Time Algorithm for Decomposing a Bubble -- 5 Conclusions and Open Problems -- References -- Critical Node Cut Parameterized by Treewidth and Solution Size is W[1]-Hard -- 1 Introduction -- 2 Preliminaries -- 3 W[1]-HardNess of SumCSP -- 4 W[1]-HardNess of CNC -- References -- Hierarchical Partial Planarity -- 1 Introduction -- 2 Preliminaries -- 3 Relationships to Other Planarity Problems -- 4 Biconnected Facial-Constrained Core Planarity -- 4.1 High-Level Description of the Algorithm -- 4.2 Detailed Description of the Algorithm -- 5 Open Problems -- References -- On the Relationship Between k-Planar and k-Quasi-Planar Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Edge Rerouting Operations and Proof Strategy -- 4 Removing Tangled (k+1)-Crossings -- 5 Removing Untangled (k+1)-Crossings -- 5.1 Obtaining (k+1)-Quasi-Planarity -- 5.2 Obtaining Simplicity -- 6 Conclusions and Open Problems -- References -- Extension Complexity of Stable Set Polytopes of Bipartite Graphs -- 1 Introduction -- 2 Rectangle Covers and Fooling Sets -- 3 An Improved Upper Bound -- 4 An Improved Lower Bound -- 5 A Small Rectangle Cover of the Special Entries -- References.
On the Number of Labeled Graphs of Bounded Treewidth -- 1 Introduction -- 2 The Construction -- 2.1 Notation and Definitions -- 2.2 Description of the Construction -- 2.3 Bounding the Treewidth -- 3 Proof of the Main Result -- 3.1 Number of Constructible Triples (, F, N) -- 3.2 Bounding the Number of Duplicates -- 3.3 Choosing the Parameter s -- 4 Concluding Remarks and Further Research -- References -- Uniquely Restricted Matchings and Edge Colorings -- 1 Introduction -- 2 Approximation Algorithms for Bipartite Graphs -- 3 Upper Bounds on ur'(G) -- 4 Concluding Remarks -- References -- Defective Coloring on Classes of Perfect Graphs -- 1 Introduction -- 2 Preliminaries and Definitions -- 3 NP-Hardness on Cographs -- 4 Polynomial Time Algorithm on Trivially Perfect Graphs -- 5 Algorithms on Cographs -- 5.1 Algorithm for Small Deficiency -- 5.2 Algorithm for Few Colors -- 5.3 Sub-Exponential Time Algorithm -- 6 Split and Chordal Graphs -- 6.1 Hardness for Bounded Deficiency -- 6.2 Hardness for Bounded Number of Colors -- 6.3 A Dynamic Programming Algorithm -- 7 Conclusions -- References -- Token Sliding on Chordal Graphs -- 1 Introduction -- 2 Hardness Results -- 2.1 Split Graphs -- 2.2 Bipartite Graphs -- 3 Interval Graphs -- 3.1 Basic Facts on Independent Sets in Interval Graphs -- 3.2 Reachability -- 3.3 Connectivity -- References -- Computing Maximum Cliques in B2-EPG Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Typed Intervals and Projection Graphs -- 3.1 Typed Intervals -- 3.2 Projection Graphs -- 4 Maximum Clique in B2-EPG Graphs -- 4.1 Graphs with Z-Vertices -- 4.2 General B2-EPG Graphs -- 5 Colorings and -boundedness -- References -- Intersection Graphs of Rays and Grounded Segments -- 1 Introduction -- 2 Preliminaries -- 3 Cycle Lemma -- 4 Stretchability -- 5 Rays and Segments -- References -- On H-Topological Intersection Graphs. 1 Introduction -- 2 Recognition of T-Graphs -- 3 Recognition Hardness -- 4 Dominating Set -- References -- The Hardness of Embedding Grids and Walls -- 1 Introduction -- 2 Preliminaries -- 2.1 From Homomorphism to Colored Embedding -- 3 Frames and Skeletons -- 4 Conclusions -- References -- Approximately Coloring Graphs Without Long Induced Paths -- 1 Introduction -- 2 Algorithm -- 3 Hardness Result -- 4 Conclusion -- References -- New and Simple Algorithms for Stable Flow Problems -- 1 Introduction -- 2 Preliminaries -- 3 A Polynomial-Time Augmenting Path Algorithm for Stable Flows -- 4 Stable Flows with Restricted Intervals -- 4.1 Forced Edges -- 4.2 Forbidden Edges -- 5 Stable Multicommodity Flows -- 5.1 Problem Simplification -- 5.2 Integral Multicommodity Stable Flows -- References -- Clique-Width and Well-Quasi-Ordering of Triangle-Free Graph Classes -- 1 Introduction -- 2 Preliminaries -- 3 Partitioning 3-Partite Graphs -- 4 Applications of Our Technique -- References -- Finding Cut-Vertices in the Square Roots of a Graph -- 1 Introduction -- 1.1 Related Work -- 1.2 Our Contributions -- 2 Preliminaries -- 2.1 Squares and Powers of Graphs -- 2.2 Graph Decompositions -- 3 Basic Properties of the Atoms in a Square -- 4 Computation of the Cut-Vertices from the Square -- 4.1 Recognition of the Essential Cut-Vertices -- 4.2 Sufficient Conditions for Non Essential Cut-Vertices -- 5 Reconstructing the Block-Cut Tree of a Square Root -- 6 Application to Trees of Cycle-Powers -- 7 Conclusion -- References -- The Minimum Shared Edges Problem on Grid-Like Graphs -- 1 Introduction -- 2 Preliminaries -- 3 On Bounded and Holey Grids -- 3.1 Bounded Grids -- 3.2 Holey Grids -- 3.3 Manhattan-Like Acyclic Digraphs -- 4 The Nonexistence of Polynomial Kernels -- 5 Conclusion -- References -- Linearly -Bounding (P6,C4)-Free Graphs -- 1 Introduction. 2 Preliminaries -- 3 The Structure of (P6,C4)-Free Atoms -- 4 -Bounding (P6,C4)-Free Graphs -- 5 A 3/2-Approximation Algorithm -- References -- Algorithms for Outerplanar Graph Roots and Graph Roots of Pathwidth at Most 2 -- 1 Introduction -- 2 Preliminaries -- 3 Outerplanar Roots -- 3.1 Structural Lemmas -- 3.2 The Algorithm -- 4 Roots of Pathwidth at Most Two -- 5 Conclusions -- References -- Enumeration and Maximum Number of Maximal Irredundant Sets for Chordal Graphs -- 1 Introduction -- 2 Preliminaries -- 3 Enumeration of Maximal Irredundant Sets for Chordal Graphs -- 4 Enumeration of Maximal Irredundant Sets for Interval Graphs -- 5 Conclusions -- References -- The Minimum Conflict-Free Row Split Problem Revisited -- 1 Introduction -- 2 Formulations in Terms of Branchings in Directed Acyclic Graphs -- 3 A Strengthening of Dilworth's Theorem and Its Connection to the MCRS Problem -- 3.1 A Min-Max Relation Strengthening Dilworth's Theorem -- 3.2 Connection with the MCRS Problem -- 4 (In)approximability Issues -- 4.1 Hardness Results -- 4.2 2-Approximating and via Laminar Set Families -- 4.3 Two Approximation Algorithms for Computing and -- 5 Conclusion -- References -- Drawing Planar Graphs with Few Geometric Primitives -- 1 Introduction -- 2 Trees with Segments on the Grid -- 3 Planar 3-Trees with Few Segments on the Grid -- 4 Maximal Outerplanar Graphs with Segments on the Grid -- 5 Triangulations and Planar Graphs with Circular Arcs -- References -- Mixed Dominating Set: A Parameterized Perspective -- 1 Introduction -- 2 Preliminaries -- 3 Algorithm for MDS Parameterized by the Solution Size -- 4 Outline of Algorithm for MDS Parameterized by Treewidth -- 5 Lower Bounds -- 6 Conclusion -- References -- Simplified Algorithmic Metatheorems Beyond MSO: Treewidth and Neighborhood Diversity -- 1 Introduction -- 1.1 Related Work. 1.2 Our Contribution -- 2 Preliminaries -- 2.1 MSO and Its Extensions -- 2.2 Treewidth and Neighborhood Diversity -- 3 Graphs of Bounded Neighborhood Diversity -- 4 XP Algorithm for MSOGL on Bounded Treewidth -- 4.1 CSP, MSO and Treewidth -- 4.2 CSP Instance Construction -- 5 Conclusions -- References -- Extending Partial Representations of Trapezoid Graphs -- 1 Introduction -- 2 Modular Decomposition and Transitive Orientations -- 3 Trapezoid Models -- 4 Extending Partial Representations of Trapezoid Posets -- 5 Extending Partial Representations of Trapezoid Graphs -- References -- On Low Rank-Width Colorings -- 1 Introduction and Main Results -- 2 Preliminaries -- 3 Powers of Sparse Graphs -- 4 Other Positive Results -- 5 Negative Results -- 6 Erdős-Hajnal property and -boundedness -- 7 Conclusions -- References -- On Strongly Chordal Graphs That Are Not Leaf Powers -- 1 Introduction -- 2 Preliminary Notions -- 3 Alternating Cycles and Quartets in Leaf Powers -- 4 Strongly Chordal Graphs That Are Not Leaf Powers -- 5 Hardness of Finding rq in Chordal Graphs -- 6 Conclusion -- References -- New Results on Weighted Independent Domination -- 1 Introduction -- 2 Preliminaries -- 2.1 Modular Decomposition -- 2.2 Antineighborhood Decomposition -- 3 WID in (P5,P5)-Free Graphs -- 3.1 Decomposition Scheme -- 3.2 Application to (P5,P5)-Free Graphs -- 4 WID in (P5, P3+P2)-Free Graphs -- 5 Concluding Remarks and Open Problems -- References -- The Parameterized Complexity of the Equidomination Problem -- 1 Introduction -- 2 Twin Relation -- 3 Properties of Twin Classes Regarding Equidomination -- 4 An XP Algorithm for the k-EQUIDOMINATION Problem -- 5 Reduction Rules -- 6 Main Results -- 7 Hereditarily Equidominating Graphs -- 8 Conclusion and Outlook -- References -- Homothetic Triangle Contact Representations -- 1 Introduction -- 2 Schnyder Woods. 3 The System of Linear Equations. |
| Record Nr. | UNINA-9910484501203321 |
| Cham : , : Springer International Publishing : , : Imprint : Springer, , 2017 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers / / edited by Hans L. Bodlaender
| Graph-Theoretic Concepts in Computer Science [[electronic resource] ] : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers / / edited by Hans L. Bodlaender |
| Edizione | [1st ed. 2003.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
| Descrizione fisica | 1 online resource (XII, 392 p.) |
| Disciplina | 511.6 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computers
Computer simulation Algorithms Data structures (Computer science) Numerical analysis Computer science—Mathematics Theory of Computation Simulation and Modeling Algorithm Analysis and Problem Complexity Data Structures Numeric Computing Discrete Mathematics in Computer Science |
| ISBN | 3-540-39890-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Lecture -- Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT -- Matching, Edge-Colouring, and Dimers -- Regular Papers -- Minimum Flow Time Graph Ordering -- Searching Is Not Jumping -- Incremental Integration Tools for Chemical Engineering: An Industrial Application of Triple Graph Grammars -- The Minimum Degree Heuristic and the Minimal Triangulation Process -- Generalized Parametric Multi-terminal Flows Problem -- Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generation -- The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes -- Tree Spanners for Bipartite Graphs and Probe Interval Graphs -- A Simple Linear Time LexBFS Cograph Recognition Algorithm -- Backbone Colorings for Networks -- Greedy Edge-Disjoint Paths in Complete Graphs -- Graph-Based Approaches to Software Watermarking -- Completely Connected Clustered Graphs -- An FPT Algorithm for Set Splitting -- Drawing Planar Graphs on a Curve -- Tree-Partitions of k-Trees with Applications in Graph Layout -- Resource Allocation Problems in Multifiber WDM Tree Networks -- An Improved Upper Bound on the Crossing Number of the Hypercube -- NCE Graph Grammars and Clique-Width -- Chordal Probe Graphs -- Subgraph Induced Planar Connectivity Augmentation -- On the Recognition of General Partition Graphs -- Short Cycles in Planar Graphs -- Complexity of Hypergraph Coloring and Seidel’s Switching -- Feedback Vertex Set and Longest Induced Path on AT-Free Graphs -- The Complexity of Graph Contractions -- Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs -- The Probabilistic Minimum Coloring Problem -- Recognizing Bipolarizable and P 4-Simplicial Graphs -- Coloring Powers of Graphs of Bounded Clique-Width -- Erratum -- Erratum: Cycles in Generalized Networks. |
| Record Nr. | UNISA-996465790903316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Graph-Theoretic Concepts in Computer Science : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers / / edited by Hans L. Bodlaender
| Graph-Theoretic Concepts in Computer Science : 29th International Workshop, WG 2003, Elspeet, The Netherlands, June 19-21, 2003, Revised Papers / / edited by Hans L. Bodlaender |
| Edizione | [1st ed. 2003.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 |
| Descrizione fisica | 1 online resource (XII, 392 p.) |
| Disciplina | 511.6 |
| Collana | Lecture Notes in Computer Science |
| Soggetto topico |
Computers
Computer simulation Algorithms Data structures (Computer science) Numerical analysis Computer science—Mathematics Theory of Computation Simulation and Modeling Algorithm Analysis and Problem Complexity Data Structures Numeric Computing Discrete Mathematics in Computer Science |
| ISBN | 3-540-39890-2 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Invited Lecture -- Blow-Ups, Win/Win’s, and Crown Rules: Some New Directions in FPT -- Matching, Edge-Colouring, and Dimers -- Regular Papers -- Minimum Flow Time Graph Ordering -- Searching Is Not Jumping -- Incremental Integration Tools for Chemical Engineering: An Industrial Application of Triple Graph Grammars -- The Minimum Degree Heuristic and the Minimal Triangulation Process -- Generalized Parametric Multi-terminal Flows Problem -- Canonical Decomposition of Outerplanar Maps and Application to Enumeration, Coding, and Generation -- The Complexity of the Matching-Cut Problem for Planar Graphs and Other Graph Classes -- Tree Spanners for Bipartite Graphs and Probe Interval Graphs -- A Simple Linear Time LexBFS Cograph Recognition Algorithm -- Backbone Colorings for Networks -- Greedy Edge-Disjoint Paths in Complete Graphs -- Graph-Based Approaches to Software Watermarking -- Completely Connected Clustered Graphs -- An FPT Algorithm for Set Splitting -- Drawing Planar Graphs on a Curve -- Tree-Partitions of k-Trees with Applications in Graph Layout -- Resource Allocation Problems in Multifiber WDM Tree Networks -- An Improved Upper Bound on the Crossing Number of the Hypercube -- NCE Graph Grammars and Clique-Width -- Chordal Probe Graphs -- Subgraph Induced Planar Connectivity Augmentation -- On the Recognition of General Partition Graphs -- Short Cycles in Planar Graphs -- Complexity of Hypergraph Coloring and Seidel’s Switching -- Feedback Vertex Set and Longest Induced Path on AT-Free Graphs -- The Complexity of Graph Contractions -- Tree Spanners, Cayley Graphs, and Diametrically Uniform Graphs -- The Probabilistic Minimum Coloring Problem -- Recognizing Bipolarizable and P 4-Simplicial Graphs -- Coloring Powers of Graphs of Bounded Clique-Width -- Erratum -- Erratum: Cycles in Generalized Networks. |
| Record Nr. | UNINA-9910768437903321 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2003 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. Federico II | ||
| ||
The Multivariate Algorithmic Revolution and Beyond [[electronic resource] ] : Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday / / edited by Hans L. Bodlaender, Rodney Downey, Fedor V. Fomin, Dániel Marx
| The Multivariate Algorithmic Revolution and Beyond [[electronic resource] ] : Essays Dedicated to Michael R. Fellows on the Occasion of His 60th Birthday / / edited by Hans L. Bodlaender, Rodney Downey, Fedor V. Fomin, Dániel Marx |
| Edizione | [1st ed. 2012.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012 |
| Descrizione fisica | 1 online resource (XXII, 506 p. 32 illus.) |
| Disciplina | 005.1 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science—Mathematics Discrete mathematics Computer science Machine theory Discrete Mathematics in Computer Science Theory of Computation Formal Languages and Automata Theory Computer Science Logic and Foundations of Programming |
| ISBN | 3-642-30891-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Record Nr. | UNISA-996465310703316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2012 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||
Parameterized and Exact Computation [[electronic resource] ] : Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings / / edited by Hans L. Bodlaender, Michael A. Langston
| Parameterized and Exact Computation [[electronic resource] ] : Second International Workshop, IWPEC 2006, Zürich, Switzerland, September 13-15, 2006, Proceedings / / edited by Hans L. Bodlaender, Michael A. Langston |
| Edizione | [1st ed. 2006.] |
| Pubbl/distr/stampa | Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 |
| Descrizione fisica | 1 online resource (XI, 279 p.) |
| Disciplina | 519.5/44 |
| Collana | Theoretical Computer Science and General Issues |
| Soggetto topico |
Algorithms
Computer science Artificial intelligence—Data processing Computer science—Mathematics Discrete mathematics Theory of Computation Data Science Discrete Mathematics in Computer Science |
| ISBN | 3-540-39101-0 |
| Formato | Materiale a stampa |
| Livello bibliografico | Monografia |
| Lingua di pubblicazione | eng |
| Nota di contenuto | Applying Modular Decomposition to Parameterized Bicluster Editing -- The Cluster Editing Problem: Implementations and Experiments -- The Parameterized Complexity of Maximality and Minimality Problems -- Parameterizing MAX SNP Problems Above Guaranteed Values -- Randomized Approximations of Parameterized Counting Problems -- Fixed-Parameter Complexity of Minimum Profile Problems -- On the OBDD Size for Graphs of Bounded Tree- and Clique-Width -- Greedy Localization and Color-Coding: Improved Matching and Packing Algorithms -- Fixed-Parameter Approximation: Conceptual Framework and Approximability Results -- On Parameterized Approximability -- Parameterized Approximation Problems -- An Exact Algorithm for the Minimum Dominating Clique Problem -- edge dominating set: Efficient Enumeration-Based Exact Algorithms -- Parameterized Complexity of Independence and Domination on Geometric Graphs -- Fixed Parameter Tractability of Independent Set in Segment Intersection Graphs -- On the Parameterized Complexity of d-Dimensional Point Set Pattern Matching -- Finding a Minimum Feedback Vertex Set in Time -- The Undirected Feedback Vertex Set Problem Has a Poly(k) Kernel -- Fixed-Parameter Tractability Results for Full-Degree Spanning Tree and Its Dual -- On the Effective Enumerability of NP Problems -- The Parameterized Complexity of Enumerating Frequent Itemsets -- Random Separation: A New Method for Solving Fixed-Cardinality Optimization Problems -- Towards a Taxonomy of Techniques for Designing Parameterized Algorithms -- Kernels: Annotated, Proper and Induced -- The Lost Continent of Polynomial Time: Preprocessing and Kernelization -- FPT at Work: Using Fixed Parameter Tractability to Solve Larger Instances of Hard Problems. |
| Record Nr. | UNISA-996466007703316 |
| Berlin, Heidelberg : , : Springer Berlin Heidelberg : , : Imprint : Springer, , 2006 | ||
| Materiale a stampa | ||
| Lo trovi qui: Univ. di Salerno | ||
| ||